Stochastic gradient descent
Part of a series on |
Machine learning and data mining |
---|
Stochastic gradient descent (often abbreviated SGD) is an
The basic idea behind stochastic approximation can be traced back to the
Background
Both
In classical statistics, sum-minimization problems arise in
The sum-minimization problem also arises for empirical risk minimization. There, is the value of the loss function at -th example, and is the empirical risk.
When used to minimize the above function, a standard (or "batch") gradient descent method would perform the following iterations:
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,
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.[4]
Iterative method
In stochastic (or "on-line") gradient descent, the true gradient of is approximated by a gradient at a single sample:
In pseudocode, stochastic gradient descent can be presented as :
- Choose an initial vector of parameters and learning rate .
- Repeat until an approximate minimum is obtained:
- Randomly shuffle samples in the training set.
- For , do:
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 of vectorization 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 of convex minimization and of stochastic approximation. Briefly, when the learning rates 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.[2][7] This is in fact a consequence of the Robbins–Siegmund theorem.[8]
Example
Suppose we want to fit a straight line to a training set with observations and corresponding estimated responses using least squares. The objective function to be minimized is
Note that in each iteration or update step, the gradient is only evaluated at a single . This is the key difference between stochastic gradient descent and batched gradient descent.
History
In 1951, Herbert Robbins and Sutton Monro introduced the earliest stochastic approximation methods, preceding stochastic gradient descent.[9] Building on this work one year later, Jack Kiefer and Jacob Wolfowitz published an optimization algorithm very close to stochastic gradient descent, using central differences as an approximation of the gradient.[10] Later in the 1950s, Frank Rosenblatt used SGD to optimize his perceptron model, demonstrating the first applicability of stochastic gradient descent to neural networks.[11]
By the 1980s,
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,[19] as of 2023 largely only include Adam-derived optimizers, as well as predecessors to Adam such as RMSprop and classic SGD. PyTorch also partially supports Limited-memory BFGS, a line-search method, but only for single-device setups without parameter groups.[18][20]
Notable applications
Stochastic gradient descent is a popular algorithm for training a wide range of models in
Stochastic gradient descent competes with the L-BFGS algorithm,[citation needed] 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.[24]
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.[25] 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.[26] Practical guidance on choosing the step size in several variants of SGD is given by Spall.[27]
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[28] by considering implicit updates whereby the stochastic gradient is evaluated at the next iterate rather than the current one:
This equation is implicit since 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:
As an example, consider least squares with features and observations . We wish to solve:
where is uniformly sampled between 1 and . 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 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:
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 depends on only through a linear combination with features , so that we can write , where may depend on as well but not on except through . Least squares obeys this rule, and so does logistic regression, and most generalized linear models. For instance, in least squares, , and in logistic regression , where is the logistic function. In Poisson regression, , and so on.
In such settings, ISGD is simply implemented as follows. Let , where is scalar. Then, ISGD is equivalent to:
The scaling factor can be found through the bisection method since in most regular models, such as the aforementioned generalized linear models, function is decreasing, and thus the search bounds for are .
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[29] and borrowed the idea from Soviet mathematician Boris Polyak's 1964 article on solving functional equations.[30] 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:[31][32]
where the parameter which minimizes 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 , thought of as a particle traveling through parameter space,
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.[35]
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[36]
AdaGrad
AdaGrad (for adaptive gradient algorithm) is a modified stochastic gradient descent algorithm with per-parameter learning rate, first published in 2011.[37] Informally, this increases the learning rate for sparser 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.[37]
It still has a base learning rate η, but this is multiplied with the elements of a vector {Gj,j} which is the diagonal of the outer product matrix
where , the gradient, at iteration τ. The diagonal is given by
While designed for convex problems, AdaGrad has been successfully applied to non-convex optimization.[38]
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.[39] 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,
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.[40]
And the parameters are updated as,
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.[39]
Adam
Adam[41] (short for Adaptive Moment Estimation) is a 2014 update to the RMSProp optimizer combining it with the main feature of the Momentum method.[42] In this optimization algorithm, running averages with exponential forgetting of both the gradients and the second moments of the gradients are used. Given parameters and a loss function , where indexes the current training iteration (indexed at ), Adam's parameter update is given by:
The initial proof establishing the convergence of Adam was incomplete, and subsequent analysis has revealed that Adam does not converge for all convex objectives.
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.[53][54]
This section needs expansion. You can help by adding to it. (June 2023) |
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 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.[55] 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.[56][57][58] (A less efficient method based on finite differences, instead of simultaneous perturbations, is given by Ruppert.[59]) Another approach to the approximation Hessian matrix is replacing it with the Fisher information matrix, which transforms usual gradient to natural.[60] 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.
Approximations in continuous time
For small learning rate stochastic gradient descent can be viewed as a discretization of the
subject to additional stochastic noise. This approximation is only valid on a finite time-horizon in the following sense: assume that all the coefficients are sufficiently smooth. Let and be a sufficiently smooth test function. Then, there exists a constant such that for all
where 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 to
for
However this SDE only approximates the one-point motion of stochastic gradient descent. For an approximation of the stochastic flow one has to consider SDEs with infinite-dimensional noise.[62]
See also
- 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
Notes
- ^ denotes the element-wise product.
References
- ISBN 978-0-262-01646-9.
- ^ ISBN 978-0-521-65263-6.
- JSTOR 2287314.
- Advances in Neural Information Processing Systems. Vol. 20. pp. 161–168.
- ^ Murphy, Kevin (2021). Probabilistic Machine Learning: An Introduction. MIT Press. Retrieved 10 April 2021.
- .
- S2CID 10043417.
- ISBN 0-12-604550-X.
- .
- .
- S2CID 12781225.
- .
- S2CID 73728964. Retrieved 2023-10-02.
- S2CID 205001834.
- ^ Duchi, John; Hazan, Elad; Singer, Yoram (2011). "Adaptive subgradient methods for online learning and stochastic optimization" (PDF). JMLR. 12: 2121–2159.
- ^ Hinton, Geoffrey. "Lecture 6e rmsprop: Divide the gradient by a running average of its recent magnitude" (PDF). p. 26. Retrieved 19 March 2020.
- ].
- ^ a b "torch.optim — PyTorch 2.0 documentation". pytorch.org. Retrieved 2023-10-02.
- S2CID 254236976.
- ^ "Module: tf.keras.optimizers | TensorFlow v2.14.0". TensorFlow. Retrieved 2023-10-02.
- ^ Jenny Rose Finkel, Alex Kleeman, Christopher D. Manning (2008). Efficient, Feature-based, Conditional Random Field Parsing. Proc. Annual Meeting of the ACL.
- ^ LeCun, Yann A., et al. "Efficient backprop." Neural networks: Tricks of the trade. Springer Berlin Heidelberg, 2012. 9-48
- ^ Jerome R. Krebs, John E. Anderson, David Hinkley, Ramesh Neelamani, Sunwoong Lee, Anatoly Baumstein, and Martin-Daniel Lacasse, (2009), "Fast full-wavefield seismic inversion using encoded sources," GEOPHYSICS 74: WCC177-WCC188.
- ^ Avi Pfeffer. "CS181 Lecture 5 — Perceptrons" (PDF). Harvard University.[permanent dead link]
- ISBN 978-0262035613.
- .
- ISBN 0-471-33052-3.
- S2CID 10279395.
- ^ S2CID 205001834.
- ^ "Gradient Descent and Momentum: The Heavy Ball Method". 13 July 2020.
- ^ Sutskever, Ilya; Martens, James; Dahl, George; Hinton, Geoffrey E. (June 2013). Sanjoy Dasgupta and David Mcallester (ed.). On the importance of initialization and momentum in deep learning (PDF). In Proceedings of the 30th international conference on machine learning (ICML-13). Vol. 28. Atlanta, GA. pp. 1139–1147. Retrieved 14 January 2016.
- ^ Sutskever, Ilya (2013). Training recurrent neural networks (PDF) (Ph.D.). University of Toronto. p. 74.
- ^ ].
- PMID 34021212.
- ^ "Papers with Code - Nesterov Accelerated Gradient Explained".
- S2CID 3548228. Archived from the original(PDF) on 2016-01-12. Retrieved 2018-02-14.
- ^ a b Duchi, John; Hazan, Elad; Singer, Yoram (2011). "Adaptive subgradient methods for online learning and stochastic optimization" (PDF). JMLR. 12: 2121–2159.
- ^ Gupta, Maya R.; Bengio, Samy; Weston, Jason (2014). "Training highly multiclass classifiers" (PDF). JMLR. 15 (1): 1461–1492.
- ^ a b Hinton, Geoffrey. "Lecture 6e rmsprop: Divide the gradient by a running average of its recent magnitude" (PDF). p. 26. Retrieved 19 March 2020.
- ^ "Understanding RMSprop — faster neural network learning". 2 September 2018.
- ^ ].
- ^ "4. Beyond Gradient Descent - Fundamentals of Deep Learning [Book]".
- arXiv:1904.09237.
- ^ Rubio, David Martínez (2017). Convergence Analysis of an Adaptive Method of Gradient Descent (PDF) (Master thesis). University of Oxford. Retrieved 5 January 2024.
- arXiv:2208.09632.
- )
- doi:10.36227/techrxiv.20427852.v1. Retrieved 2022-11-19.)
{{cite journal}}
: Cite journal requires|journal=
(help - OCLC 1333722169.)
{{cite book}}
: CS1 maint: multiple names: authors list (link - )
- )
- ^ "An overview of gradient descent optimization algorithms". 19 January 2016.
- )
- ^ Balles, Lukas; Hennig, Philipp (15 February 2018). "Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradients".
- ^ "SignSGD: Compressed Optimisation for Non-Convex Problems". 3 July 2018. pp. 560–569.
- S2CID 12396034.
- .
- S2CID 3564529.
- ISBN 978-1-4471-4284-3.
- .
- S2CID 207585383.
- ISSN 1533-7928.
- ^
Gess, Benjamin; Kassing, Sebastian; Konarovskyi, Vitalii (14 February 2023). "Stochastic Modified Flows, Mean-Field Limits and Dynamics of Stochastic Gradient Descent". arXiv:2302.07125 [math.PR].
Further reading
- 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
- ISBN 978-3-642-35288-1
- Spall, James C. (2003), Introduction to Stochastic Search and Optimization, 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. Archived from the original on 2021-12-22 – via YouTube.
- Goh (April 4, 2017). "Why Momentum Really Works". . Interactive paper explaining momentum.