Stochastic gradient descent (often abbreviatedSGD) is aniterative method for optimizing anobjective function with suitablesmoothness properties (e.g.differentiable orsubdifferentiable). It can be regarded as astochastic approximation ofgradient descent optimization, since it replaces the actual gradient (calculated from the entiredata set) by an estimate thereof (calculated from a randomly selected subset of the data). Especially inhigh-dimensional optimization problems this reduces the very highcomputational burden, achieving faster iterations in exchange for a lowerconvergence rate.^[1]

The basic idea behind stochastic approximation can be traced back to the Robbins–Monro algorithm of the 1950s. Today, stochastic gradient descent has become an important optimization method inmachine learning.^[2]

Bothstatisticalestimation andmachine learning consider the problem ofminimizing anobjective function that has the form of a sum:$${\displaystyle Q(w)=\frac{1}{n}\sum _{i=1}^n{Q}_i(w),}$$where theparameter${\displaystyle w}$ that minimizes${\displaystyle Q(w)}$ is to beestimated. Each summand function${\displaystyle Q_i}$ is typically associated with the${\displaystyle i}$-thobservation in thedata set (used for training).

In classical statistics, sum-minimization problems arise inleast squares and inmaximum-likelihood estimation (for independent observations). The general class of estimators that arise as minimizers of sums are calledM-estimators. However, in statistics, it has been long recognized that requiring even local minimization is too restrictive for some problems of maximum-likelihood estimation.^[3] Therefore, contemporary statistical theorists often considerstationary points of thelikelihood function (or zeros of its derivative, thescore function, and otherestimating equations).

The sum-minimization problem also arises forempirical risk minimization. There,${\displaystyle Q_i(w)}$ is the value of theloss function at${\displaystyle i}$-th example, and${\displaystyle 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:$${\displaystyle w:=w-\eta \mathrm{\nabla }Q(w)=w-\frac{\eta }{n}\sum _{i=1}^n\mathrm{\nabla }{Q}_i(w).}$$The step size is denoted by${\displaystyle \eta }$ (sometimes called thelearning rate in machine learning) and here "${\displaystyle :=}$" denotes the update of a variable in the algorithm.

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 descentsamples a subset of summand functions at every step. This is very effective in the case of large-scale machine learning problems.^[4]

In stochastic (or "on-line") gradient descent, the true gradient of${\displaystyle Q(w)}$ is approximated by a gradient at a single sample:$${\displaystyle w:=w-\eta \mathrm{\nabla }{Q}_i(w).}$$As the algorithm sweeps through the training set, it performs the above update for each training sample. 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 anadaptive learning rate so that the algorithm converges.^[5]

In pseudocode, stochastic gradient descent can be presented as :

A compromise between computing the true gradient and the gradient at a single sample is to compute the gradient against more than one training sample (called a "mini-batch") at each step. This can perform significantly better than "true" stochastic gradient descent described, because the code can make use ofvectorization libraries rather than computing each step separately as was first shown in^[6] where it was called "the bunch-mode back-propagation algorithm". It may also result in smoother convergence, as the gradient computed at each step is averaged over more training samples.

The convergence of stochastic gradient descent has been analyzed using the theories ofconvex minimization and ofstochastic approximation. Briefly, when thelearning rates${\displaystyle \eta }$ decrease with an appropriate rate,and subject to relatively mild assumptions, stochastic gradient descent convergesalmost surely to a global minimum when the objective function isconvex orpseudoconvex, and otherwise converges almost surely to a local minimum.^[2][7]This is in fact a consequence of theRobbins–Siegmund theorem.^[8]

Suppose we want to fit a straight line${\displaystyle \hat{y}=w_1+w_{2}x}$ to a training set with observations${\displaystyle ((x_1,y_1),(x_2,y_2)\dots ,(x_n,y_n))}$ and corresponding estimated responses${\displaystyle ({\hat{y}}_1,{\hat{y}}_2,\dots ,{\hat{y}}_n)}$ usingleast squares. The objective function to be minimized is$${\displaystyle 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:$${\displaystyle \left[\begin{array}{c}{w}_1\\ w_2\end{array}\right]\leftarrow \left[\begin{array}{c}{w}_1\\ w_2\end{array}\right]-\eta \left[\begin{array}{c}\frac{\mathrm{\partial }}{\mathrm{\partial }{w}_1}(w_1+w_2{x}_i-y_i{)}^2\\ \frac{\mathrm{\partial }}{\mathrm{\partial }{w}_2}(w_1+w_2{x}_i-y_i{)}^2\end{array}\right]=\left[\begin{array}{c}{w}_1\\ w_2\end{array}\right]-\eta \left[\begin{array}{c}2(w_1+w_2{x}_i-y_i)\\ 2x_i(w_1+w_2{x}_i-y_i)\end{array}\right].}$$Note that in each iteration or update step, the gradient is only evaluated at a single${\displaystyle x_i}$. This is the key difference between stochastic gradient descent and batched gradient descent.

In general, given a linear regression${\displaystyle \hat{y}=\sum _{k\in 1:m}{w}_k{x}_k}$ problem, stochastic gradient descent behaves differently when (underparameterized) and${\displaystyle m\ge n}$ (overparameterized). In the overparameterized case, stochastic gradient descent converges to${\displaystyle \arg \underset{w:w^T{x}_k=y_k\mathrm{\forall }k\in 1:n}{min}\Vert w-w_0\Vert }$. That is, SGD converges to the interpolation solution with minimum distance from the starting${\displaystyle w_0}$. This is true even when the learning rate remains constant. In the underparameterized case, SGD does not converge if learning rate remains constant.^[9]

In 1951,Herbert Robbins andSutton Monro introduced the earliest stochastic approximation methods, preceding stochastic gradient descent.^[10] Building on this work one year later,Jack Kiefer andJacob Wolfowitz publishedan optimization algorithm very close to stochastic gradient descent, usingcentral differences as an approximation of the gradient.^[11] Later in the 1950s,Frank Rosenblatt used SGD to optimize hisperceptron model, demonstrating the first applicability of stochastic gradient descent to neural networks.^[12]

Backpropagation was first described in 1986, with stochastic gradient descent being used to efficiently optimize parameters across neural networks with multiplehidden layers. Soon after, another improvement was developed: mini-batch gradient descent, where small batches of data are substituted for single samples. In 1997, the practical performance benefits from vectorization achievable with such small batches were first explored,^[13] paving the way for efficient optimization in machine learning. As of 2023, this mini-batch approach remains the norm for training neural networks, balancing the benefits of stochastic gradient descent withgradient descent.^[14]

By the 1980s,momentum had already been introduced, and was added to SGD optimization techniques in 1986.^[15] However, these optimization techniques assumed constanthyperparameters, i.e. a fixed learning rate and momentum parameter. In the 2010s, adaptive approaches to applying SGD with a per-parameter learning rate were introduced with AdaGrad (for "Adaptive Gradient") in 2011^[16] and RMSprop (for "Root Mean Square Propagation") in 2012.^[17] In 2014, Adam (for "Adaptive Moment Estimation") was published, applying the adaptive approaches of RMSprop to momentum; many improvements and branches of Adam were then developed such as Adadelta, Adagrad, AdamW, and Adamax.^[18][19]

Within machine learning, approaches to optimization in 2023 are dominated by Adam-derived optimizers. TensorFlow and PyTorch, by far the most popular machine learning libraries,^[20] as of 2023 largely only include Adam-derived optimizers, as well as predecessors to Adam such as RMSprop and classic SGD. PyTorch also partially supportslimited-memory BFGS, a line-search method, but only for single-device setups without parameter groups.^[19][21]

Stochastic gradient descent is a popular algorithm for training a wide range of models inmachine learning, including (linear)support vector machines,logistic regression (see, e.g.,Vowpal Wabbit) andgraphical models.^[22] When combined with thebackpropagation algorithm, it is thede facto standard algorithm for trainingartificial neural networks.^[23] Its use has been also reported in theGeophysics community, specifically to applications of Full Waveform Inversion (FWI).^[24]

Stochastic gradient descent competes with theL-BFGS algorithm,^{[citation needed]} which is also widely used. Stochastic gradient descent has been used since at least 1960 for traininglinear regression models, originally under the nameADALINE.^[25]

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

Many improvements on the basic stochastic gradient descent algorithm have been proposed and used. In particular, in machine learning, the need to set alearning 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.^[26] A conceptually simple extension of stochastic gradient descent makes the learning rate a decreasing functionη_t of the iteration numbert, giving alearning 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 onk-means clustering.^[27] Practical guidance on choosing the step size in several variants of SGD is given by Spall.^[28]

As mentioned earlier, classical stochastic gradient descent is generally sensitive tolearning rateη. Fast convergence requires large learning rates but this may induce numerical instability. The problem can be largely solved^[29] by consideringimplicit updates whereby the stochastic gradient is evaluated at the next iterate rather than the current one:$${\displaystyle w^{\text{new}}:=w^{\text{old}}-\eta \mathrm{\nabla }{Q}_i(w^{\text{new}}).}$$

This equation is implicit since${\displaystyle w^{\text{new}}}$ appears on both sides of the equation. It is a stochastic form of theproximal gradient method since the updatecan also be written as:$${\displaystyle w^{\text{new}}:=\arg \underset{w}{min}\left\{Q_i(w)+\frac{1}{2\eta }{\Vert w-w^{\text{old}}\Vert }^2\right\}.}$$

As an example, consider least squares with features${\displaystyle x_1,\dots ,x_n\in {\mathbb{R}}^p}$ and observations${\displaystyle y_1,\dots ,y_n\in \mathbb{R}}$. We wish to solve:$${\displaystyle \underset{w}{min}\sum _{j=1}^n{\left(y_j-x_j^{\prime }w\right)}^2,}$$where${\displaystyle x_j^{\prime }w=x_{j1}{w}_1+x_{j,2}{w}_2+...+x_{j,p}{w}_p}$ indicates the inner product.Note that${\displaystyle x}$ could have "1" as the first element to include an intercept. Classical stochastic gradient descent proceeds as follows:$${\displaystyle w^{\text{new}}=w^{\text{old}}+\eta \left(y_i-x_i^{\prime }{w}^{\text{old}}\right)x_i}$$

where${\displaystyle i}$ is uniformly sampled between 1 and${\displaystyle n}$. Although theoretical convergence of this procedure happens under relatively mild assumptions, in practice the procedure can be quite unstable. In particular, when${\displaystyle \eta }$ is misspecified so that${\displaystyle I-\eta x_i{x}_i^{\prime }}$ 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:$${\displaystyle w^{\text{new}}=w^{\text{old}}+\frac{\eta }{1+\eta {\Vert x_i\Vert }^2}\left(y_i-x_i^{\prime }{w}^{\text{old}}\right)x_i.}$$

This procedure will remain numerically stable virtually for all${\displaystyle \eta }$ as thelearning rate is now normalized. Such comparison between classical and implicit stochastic gradient descent in the least squares problem is very similar to the comparison betweenleast mean squares (LMS) andnormalized 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${\displaystyle Q_i(w)}$ depends on${\displaystyle w}$ only through a linear combination with features${\displaystyle x_i}$, so that we can write${\displaystyle {\mathrm{\nabla }}_w{Q}_i(w)=-q(x_i^{\prime }w)x_i}$, where${\displaystyle q()\in \mathbb{R}}$ may depend on${\displaystyle x_i,y_i}$ as well but not on${\displaystyle w}$ except through${\displaystyle x_i^{\prime }w}$. Least squares obeys this rule, and so doeslogistic regression, and mostgeneralized linear models. For instance, in least squares,${\displaystyle q(x_i^{\prime }w)=y_i-x_i^{\prime }w}$, and in logistic regression${\displaystyle q(x_i^{\prime }w)=y_i-S(x_i^{\prime }w)}$, where${\displaystyle S(u)=e^u/(1+e^u)}$ is thelogistic function. InPoisson regression,${\displaystyle q(x_i^{\prime }w)=y_i-e^{x_i^{\prime }w}}$, and so on.

In such settings, ISGD is simply implemented as follows. Let${\displaystyle f(\xi )=\eta q(x_i^{\prime }{w}^{\text{old}}+\xi \Vert x_i{\Vert }^2)}$, where${\displaystyle \xi }$ is scalar.Then, ISGD is equivalent to:$${\displaystyle w^{\text{new}}=w^{\text{old}}+{\xi }^{\ast }{x}_i,\text{where}{\xi }^{\ast }=f({\xi }^{\ast }).}$$

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

Further proposals include themomentum method or theheavy ball method, which in ML context appeared inRumelhart,Hinton andWilliams' paper on backpropagation learning^[30] and borrowed the idea from Soviet mathematician Boris Polyak's 1964 article on solving functional equations.^[31] Stochastic gradient descent with momentum remembers the updateΔw at each iteration, and determines the next update as alinear combination of the gradient and the previous update:^[32][33]$${\displaystyle \mathrm{\Delta }w:=\alpha \mathrm{\Delta }w-\eta \mathrm{\nabla }{Q}_i(w)}$$$${\displaystyle w:=w+\mathrm{\Delta }w}$$that leads to:$${\displaystyle w:=w-\eta \mathrm{\nabla }{Q}_i(w)+\alpha \mathrm{\Delta }w}$$

where theparameter${\displaystyle w}$ which minimizes${\displaystyle Q(w)}$ is to beestimated,${\displaystyle \eta }$ is a step size (sometimes called thelearning rate in machine learning) and${\displaystyle \alpha }$ is an exponentialdecay factor between 0 and 1 that determines the relative contribution of the current gradient and earlier gradients to the weight change.

The name momentum stems from an analogy tomomentum in physics: the weight vector${\displaystyle w}$, thought of as a particle traveling through parameter space,^[30] 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 ofartificial neural networks for several decades.^[34]Themomentum method is closely related tounderdamped Langevin dynamics, and may be combined withsimulated annealing.^[35]

In mid-1980s the method was modified byYurii Nesterov to use the gradient predicted at the next point, and the resulting so-calledNesterov Accelerated Gradient was sometimes used in ML in the 2010s.^[36]

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^[37]

$${\displaystyle \overline{w}=\frac{1}{t}\sum _{i=0}^{t-1}{w}_i.}$$When optimization is done, this averaged parameter vector takes the place ofw.

AdaGrad (for adaptivegradient algorithm) is a modified stochastic gradient descent algorithm with per-parameterlearning rate, first published in 2011.^[38] Informally, this increases the learning rate forsparser parameters^{[clarification needed]} 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.^[38]

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 theouter product matrix

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

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

$${\displaystyle G_{j,j}=\sum _{\tau =1}^t{g}_{\tau ,j}^2.}$$This vector essentially stores a historical sum of gradient squares by dimension and is updated after every iteration. The formula for an update is now^[a]$${\displaystyle w:=w-\eta \mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(G{)}^{-\frac{1}{2}}\odot g}$$or, written as per-parameter updates,$${\displaystyle 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 parameterw_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.^[34]

While designed forconvex problems, AdaGrad has been successfully applied to non-convex optimization.^[39]

RMSProp (for Root Mean Square Propagation) is a method invented in 2012 by James Martens andIlya Sutskever, at the time both PhD students in Geoffrey Hinton's group, in which thelearning rate is, like in Adagrad, 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.^[40] Unusually, it was not published in an article but merely described in aCoursera lecture.^{[citation needed][41][42]}

So, first the running average is calculated in terms of means square,

$${\displaystyle v(w,t):=\gamma v(w,t-1)+\left(1-\gamma \right){\left(\mathrm{\nabla }{Q}_i(w)\right)}^2}$$

where,${\displaystyle \gamma }$ is the forgetting factor. The concept of storing the historical gradient as sum of squares is borrowed from Adagrad, but "forgetting" is introduced to solve Adagrad's diminishing learning rates in non-convex problems by gradually decreasing the influence of old data.^{[citation needed]}

And the parameters are updated as,

$${\displaystyle w:=w-\frac{\eta }{\sqrt{v(w,t)}}\mathrm{\nabla }{Q}_i(w)}$$

RMSProp has shown good adaptation of learning rate in different applications. RMSProp can be seen as a generalization ofRprop and is capable to work with mini-batches as well opposed to only full-batches.^[40]

Adam^[43] (short for Adaptive Moment Estimation) is a 2014 update to theRMSProp optimizer combining it with the main feature of theMomentum method.^[44] In this optimization algorithm, running averages with exponential forgetting of both the gradients and the second moments of the gradients are used. Given parameters${\displaystyle w^{(t)}}$ and a loss function${\displaystyle L^{(t)}}$, where${\displaystyle t}$ indexes the current training iteration (indexed at${\displaystyle 1}$), Adam's parameter update is given by:

$${\displaystyle m_w^{(t)}:={\beta }_1{m}_w^{(t-1)}+\left(1-{\beta }_1\right){\mathrm{\nabla }}_w{L}^{(t-1)}}$$$${\displaystyle v_w^{(t)}:={\beta }_2{v}_w^{(t-1)}+\left(1-{\beta }_2\right){\left({\mathrm{\nabla }}_w{L}^{(t-1)}\right)}^2}$$

$${\displaystyle {\hat{m}}_w^{(t)}=\frac{m_w^{(t)}}{1-{\beta }_1^t}}$$$${\displaystyle {\hat{v}}_w^{(t)}=\frac{v_w^{(t)}}{1-{\beta }_2^t}}$$

$${\displaystyle w^{(t)}:=w^{(t-1)}-\eta \frac{{\hat{m}}_w^{(t)}}{\sqrt{{\hat{v}}_w^{(t)}}+\epsilon }}$$where${\displaystyle \epsilon }$ is a small scalar (e.g.${\displaystyle {10}^{-8}}$) used to prevent division by 0, and${\displaystyle {\beta }_1}$ (e.g. 0.9) and${\displaystyle {\beta }_2}$ (e.g. 0.999) are the forgetting factors for gradients and second moments of gradients, respectively. Squaring and square-rooting is done element-wise.

As the exponential moving averages of the gradient${\displaystyle m_w^{(t)}}$ and the squared gradient${\displaystyle v_w^{(t)}}$ are initialized with a vector of 0's, there would be a bias towards zero in the first training iterations. A factor${\displaystyle \frac{1}{1-{\beta }_{1/2}^t}}$ is introduced to compensate this bias and get better estimates${\displaystyle {\hat{m}}_w^{(t)}}$ and${\displaystyle {\hat{v}}_w^{(t)}}$.

The initial proof establishing the convergence of Adam was incomplete, and subsequent analysis has revealed that Adam does not converge for all convex objectives.^[45][46] Despite this,Adam continues to be used due to its strong performance in practice.^[47]

The popularity ofAdam inspired many variants and enhancements. Some examples include:

• Nesterov-enhanced gradients:NAdam,^[48]FASFA^[49]
• varying interpretations of second-order information:Powerpropagation^[50] andAdaSqrt.^[51]
• Usinginfinity norm:AdaMax^[43]
• AMSGrad,^[52] which improves convergence overAdam by using maximum of past squared gradients instead of the exponential average.^[53]AdamX^[54] further improves convergence overAMSGrad.
• AdamW,^[55] which improves theweight decay.

Even though sign-based optimization goes back to the aforementionedRprop, in 2018 researchers tried to simplify Adam by removing the magnitude of the stochastic gradient from being taken into account and only considering its sign.^[56][57]

This sectionneeds expansion. You can help byadding to it.(June 2023)

Backtracking line search is another variant of gradient descent. All of the below are sourced from the mentioned link. It is based on a condition known as the Armijo–Goldstein condition. Both methods allow learning rates to change at each iteration; however, the manner of the change is different. Backtracking line search uses function evaluations to check Armijo's condition, and in principle the loop in the algorithm for determining the learning rates can be long and unknown in advance. Adaptive SGD does not need a loop in determining learning rates. On the other hand, adaptive SGD does not guarantee the "descent property" – which Backtracking line search enjoys – which is that${\displaystyle f(x_{n+1})\le f(x_n)}$ for all n. If the gradient of the cost function is globally Lipschitz continuous, with Lipschitz constant L, and learning rate is chosen of the order 1/L, then the standard version of SGD is a special case of backtracking line search.

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^{[citation needed]}. A method that uses direct measurements of theHessian matrices of the summands in the empirical risk function was developed by Byrd, Hansen, Nocedal, and Singer.^[58] 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.^[59][60][61] (A less efficient method based on finite differences, instead of simultaneous perturbations, is given by Ruppert.^[62]) Another approach to the approximation Hessian matrix is replacing it with the Fisher information matrix, which transforms usual gradient to natural.^[63] 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. When the objective is a nonlinear least-squares loss$${\displaystyle Q(w)=\frac{1}{n}\sum _{i=1}^n{Q}_i(w)=\frac{1}{n}\sum _{i=1}^n(m(w;x_i)-y_i{)}^2,}$$ where${\displaystyle m(w;x_i)}$ is the predictive model (e.g., adeep neural network)the objective's structure can be exploited to estimate 2nd order information using gradients only. The resulting methods are simple and often effective^[64]

For small learning rate$\eta$ stochastic gradient descent$(w_n{)}_{n\in {\mathbb{N}}_0}$ can be viewed as a discretization of thegradient flow ODE

$${\displaystyle \frac{d}{dt}{W}_t=-\mathrm{\nabla }Q(W_t)}$$

subject to additional stochastic noise. This approximation is only valid on a finite time-horizon in the following sense: assume that all the coefficients$Q_i$ are sufficiently smooth. Let$T>0$ and$g:{\mathbb{R}}^d\to \mathbb{R}$ be a sufficiently smooth test function. Then, there exists a constant$C>0$ such that for all$\eta >0$

$${\displaystyle \underset{k=0,\dots ,\lfloor T/\eta \rfloor }{max}\left|\mathbb{E}[g(w_k)]-g(W_{k\eta })\right|\le C\eta ,}$$

where$\mathbb{E}$ denotes taking the expectation with respect to the random choice of indices in the stochastic gradient descent scheme.

Since this approximation does not capture the random fluctuations around the mean behavior of stochastic gradient descent solutions tostochastic differential equations (SDEs) have been proposed as limiting objects.^[65] More precisely, the solution to the SDE

$${\displaystyle d{W}_t=-\mathrm{\nabla }\left(Q(W_t)+\frac{1}{4}\eta |\mathrm{\nabla }Q(W_t){|}^2\right)dt+\sqrt{\eta }\mathrm{\Sigma }(W_t{)}^{1/2}d{B}_t,}$$

for$${\displaystyle \mathrm{\Sigma }(w)=\frac{1}{n^2}\left(\sum _{i=1}^n{Q}_i(w)-Q(w)\right){\left(\sum _{i=1}^n{Q}_i(w)-Q(w)\right)}^T}$$ where$d{B}_t$ denotes theIto-integral with respect to aBrownian motion is a more precise approximation in the sense that there exists a constant$C>0$ such that

$${\displaystyle \underset{k=0,\dots ,\lfloor T/\eta \rfloor }{max}\left|\mathbb{E}[g(w_k)]-\mathbb{E}[g(W_{k\eta })]\right|\le C{\eta }^2.}$$

However this SDE only approximates the one-point motion of stochastic gradient descent. For an approximation of thestochastic flow one has to consider SDEs with infinite-dimensional noise.^[66]

• Backtracking line search
• Broken Neural Scaling Law
• Coordinate descent – changes one coordinate at a time, rather than one example
• Linear classifier
• Online machine learning
• Stochastic hill climbing
• Stochastic variance reduction

• Bottou, Léon (2004),"Stochastic Learning",Advanced Lectures on Machine Learning, LNAI, vol. 3176, Springer, pp. 146–168,ISBN 978-3-540-23122-6
• Buduma, Nikhil; Locascio, Nicholas (2017),"Beyond Gradient Descent",Fundamentals of Deep Learning : Designing Next-Generation Machine Intelligence Algorithms, O'Reilly,ISBN 9781491925584
• LeCun, Yann A.; Bottou, Léon; Orr, Genevieve B.;Müller, Klaus-Robert (2012),"Efficient BackProp",Neural Networks: Tricks of the Trade, Springer, pp. 9–48,ISBN 978-3-642-35288-1
• Spall, James C. (2003),Introduction to Stochastic Search and Optimization,Wiley,ISBN 978-0-471-33052-3

• "Gradient Descent, How Neural Networks Learn".3Blue1Brown. October 16, 2017.Archived from the original on 2021-12-22 – viaYouTube.
• Goh (April 4, 2017)."Why Momentum Really Works".Distill.2 (4).doi:10.23915/distill.00006. Interactive paper explaining momentum.

• Stochastic optimization
• Computational statistics
• Gradient methods
• M-estimators
• Machine learning algorithms
• Convex optimization
• Statistical approximations

• All articles with dead external links
• Articles with dead external links from June 2018
• Articles with permanently dead external links
• CS1 errors: missing periodical
• CS1 maint: multiple names: authors list
• Articles with short description
• Short description is different from Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from July 2015
• Wikipedia articles needing clarification from November 2023
• Articles with unsourced statements from June 2023
• Articles with unsourced statements from June 2024
• Articles to be expanded from June 2023
• All articles to be expanded
• Articles with unsourced statements from April 2020