Stochastic gradient descent

Stochastic gradient descent (often abbreviated SGD) is a way to make things better by solving problems step by step. It is used to find the best answer for some math questions that can be really tricky.

Instead of looking at all the information at once, SGD looks at small, random pieces of the information. This makes it faster to work through big problems, but it might take more steps to get the perfect answer.

The idea behind this method started in the 1950s with something called the Robbins–Monro algorithm. Today, stochastic gradient descent is very important in machine learning, where computers learn from data to get smarter.

Background

Main article: M-estimation

See also: Estimating equation

Both statistical estimation and machine learning look at the problem of making something smaller. This something is called an objective function, and it is made up of a sum of smaller parts. Each smaller part is linked to one piece of information in a group of data.

When we want to make this sum smaller, a common way is to use a method called gradient descent. This method looks at all the pieces of data at once to decide how to change things. But sometimes, especially with very large amounts of data, looking at every piece at once can take a lot of time.

To save time, a method called stochastic gradient descent is used. Instead of looking at all the data, it looks at just a small, random part of the data each time. This makes the process faster and is very helpful when dealing with big machine learning problems.

Iterative method

Stochastic gradient descent is a method used to find the best solution for a problem by making small changes step by step. Instead of using all the data at once, it looks at one piece of data at a time. This makes the process faster and can help avoid getting stuck.

The method starts with an initial guess and a learning rate, which controls how big each step is. It then goes through the data many times, updating the guess each time based on one random piece of data. Sometimes, a few pieces of data are used together to get a better result. This helps the method work more smoothly and reach a good solution.

Linear regression

We can try to draw a straight line to match a set of points. This line has numbers that we change to make it fit better. One way to do this is called stochastic gradient descent.

In this method, instead of looking at all points at once, we look at one point at a time to decide how to change the line. This makes the process faster and can help us find a good fit for the line.

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. Practical guidance on choosing the step size in several variants of SGD is given by Spall.

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 − η ∇ 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 ) + 1 2 η ‖ w − w old ‖ 2 } .

As an example, consider least squares with features x 1 , … , x n ∈ R p and observations y 1 , … , y n ∈ R . We wish to solve: min w ∑ j = 1 n ( y j − x j ′ w ) 2 , where x j ′ w = x j 1 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 + η ( 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 η is misspecified so that I − η 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 + η 1 + η ‖ x i ‖ 2 ( y i − x i ′ w old ) x i .

This procedure will remain numerically stable virtually for all η 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 ∇ w Q i ( w ) = − q ( x i ′ w ) x i , where q ( ) ∈ 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 ( ξ ) = η q ( x i ′ w old + ξ ‖ x i ‖ 2 ) , where ξ is scalar. Then, ISGD is equivalent to: w new = w old + ξ ∗ x i ,   where   ξ ∗ = f ( ξ ∗ ) .

The scaling factor ξ ∗ ∈ 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 ξ ∗ are [ min ( 0 , f ( 0 ) ) , max ( 0 , f ( 0 ) ) ] .

Momentum

Further proposals include the momentum method or the heavy ball method, which in ML context appeared in Rumelhart, Hinton and Williams' paper on backpropagation learning and borrowed the idea from Soviet mathematician Boris Polyak's 1964 article on solving functional equations. 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: Δ w := α Δ w − η ∇ Q i ( w ) w := w + Δ w that leads to: w := w − η ∇ Q i ( w ) + α Δ w

where the parameter w which minimizes Q ( w ) is to be estimated, η is a step size (sometimes called the learning rate in machine learning) and α is an exponential decay 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 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. The momentum method is closely related to underdamped Langevin dynamics, and may be combined with simulated annealing.

In mid-1980s the method was modified by Yurii Nesterov to use the gradient predicted at the next point, and the resulting so-called Nesterov Accelerated Gradient was sometimes used in ML in the 2010s.

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

w ¯ = 1 t ∑ 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 = ∑ τ = 1 t g τ g τ T where g τ = ∇ Q i ( w ) , the gradient, at iteration τ. The diagonal is given by

G j , j = ∑ τ = 1 t g τ , 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 w := w − η d i a g ( G ) − 1 2 ⊙ g or, written as per-parameter updates, w j := w j − η 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, G i = ∑ τ = 1 t g τ 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 a method invented in 2012 by James Martens and Ilya Sutskever, at the time both PhD students in Geoffrey Hinton's group, in which the learning 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. Unusually, it was not published in an article but merely described in a Coursera lecture.^{[citation needed]}

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

v ( w , t ) := γ v ( w , t − 1 ) + ( 1 − γ ) ( ∇ Q i ( w ) ) 2 where, γ 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,

w := w − η v ( w , t ) ∇ Q i ( w )

RMSProp has shown good 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 a 2014 update to the RMSProp optimizer combining it with the main feature of the Momentum method. In this optimization algorithm, running averages with exponential forgetting 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 1 ), Adam's parameter update is given by:

m w ( t ) := β 1 m w ( t − 1 ) + ( 1 − β 1 ) ∇ w L ( t − 1 ) v w ( t ) := β 2 v w ( t − 1 ) + ( 1 − β 2 ) ( ∇ w L ( t − 1 ) ) 2

m ^ w ( t ) = m w ( t ) 1 − β 1 t v ^ w ( t ) = v w ( t ) 1 − β 2 t

w ( t ) := w ( t − 1 ) − η m ^ w ( t ) v ^ w ( t ) + ε where ε is a small scalar (e.g. 10 − 8 ) used to prevent division by 0, and β 1 (e.g. 0.9) and β 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 m w ( t ) and the squared gradient 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 1 1 − β 1 / 2 t is introduced to compensate this bias and get better estimates m ^ w ( t ) and 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. Despite this, Adam continues to be used due to its strong performance in practice.

Variants

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

• Nesterov-enhanced gradients: NAdam, FASFA
• varying interpretations of second-order information: Powerpropagation and AdaSqrt.
• Using infinity norm: AdaMax
• AMSGrad, which improves convergence over Adam by using maximum of past squared gradients instead of the exponential average. AdamX further improves convergence over AMSGrad.
• AdamW, which improves the weight decay.

Sign-based stochastic gradient descent

Even though sign-based optimization goes back to the aforementioned Rprop, 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. This results in a significantly lower communication cost of transferring gradients from workers to the parameter server. In this sense, it serves to better compress the gradient information, while having comparable convergence to standard SGD.

Backtracking line search

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 f ( x n + 1 ) ≤ 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.

Second-order methods

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 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.) Another approach to the approximation Hessian matrix is replacing it with the Fisher information matrix, which transforms usual gradient to natural. 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 Q ( w ) = 1 n ∑ i = 1 n Q i ( w ) = 1 n ∑ i = 1 n ( m ( w ; x i ) − y i ) 2 , where m ( w ; x i ) is the predictive model (e.g., a deep 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

Approximations in continuous time

For small learning rates, stochastic gradient descent can be seen as a simplified version of a mathematical process called gradient flow. This method includes some random noise, making it different from the exact calculation.

Researchers have suggested using special math tools called stochastic differential equations to better understand the random movements in stochastic gradient descent. These tools provide a closer match to how the method behaves over time. However, they only capture part of the picture and need more complex models to fully describe all the random changes.