Momentum - Revision history

Tcl74 at 00:24, 16 December 2021

2021-12-16T00:24:06Z

← Older revision		Revision as of 20:24, 15 December 2021
Line 156:		Line 156:
	</math>		</math>

	<math>b_i=\mub_{i-1}+g_i		<math>b_i=\mu*b_{i-1}+g_i
	</math>		</math>

Eh672: /* SGD with Momentum */

2021-12-15T00:06:07Z

SGD with Momentum

← Older revision		Revision as of 20:06, 14 December 2021
Line 150:		Line 150:
	</math> and the same parameters as the previous example, with learning rate of <math>\gamma=0.05		</math> and the same parameters as the previous example, with learning rate of <math>\gamma=0.05
	</math> and starting point of <math>\theta_0=-2.8		</math> and starting point of <math>\theta_0=-2.8
	</math>. The solver iterates through the following equations:		</math>. The solver iterates through the following equations:

	<math>g_i = \nabla\theta_i f_i (\theta_{i-1}) = 1.2\theta_{i-1}^3 - 0.3\theta_{i-1}^2 - 4*\theta_{i-1} - 0.8		<math>g_i = \nabla\theta_i f_i (\theta_{i-1}) = 1.2\theta_{i-1}^3 - 0.3\theta_{i-1}^2 - 4*\theta_{i-1} - 0.8

Eh672: /* SGD with Momentum */

2021-12-12T17:56:52Z

SGD with Momentum

← Older revision		Revision as of 13:56, 12 December 2021
Line 221:		Line 221:
	\|<nowiki>-0.676</nowiki>		\|<nowiki>-0.676</nowiki>
	\|<nowiki>-0.279</nowiki>		\|<nowiki>-0.279</nowiki>
	\|-
	\|5
	~~\| -0.431~~
	~~\| -0.008~~
	\|-		\|-
	\|		\|

Tcl74 at 02:20, 10 December 2021

2021-12-10T02:20:15Z

← Older revision		Revision as of 22:20, 9 December 2021
Line 8:		Line 8:

	=== Algorithm ===		=== Algorithm ===
	The main idea behind momentum is to compute an exponentially weighted average of the gradients and use that to update the weights. By taking past gradients into account, the steps to gradient descent become smoothed out, which can reduce the amount of ~~"zig zagging"~~ seen in iterations (where the iterative solutions are going between above and below the true curve). <ref>Kevin P. Murphy. ''Machine Learning : A Probabilistic Perspective''. The MIT Press; 2012. https://search-ebscohost-com.proxy.library.cornell.edu/login.aspx?direct=true&db=nlebk&AN=480968&site=ehost-live</ref>		The main idea behind momentum is to compute an exponentially weighted average of the gradients and use that to update the weights. By taking past gradients into account, the steps to gradient descent become smoothed out, which can reduce the amount of oscillations seen in iterations (where the iterative solutions are going between above and below the true curve). <ref>Kevin P. Murphy. ''Machine Learning : A Probabilistic Perspective''. The MIT Press; 2012. https://search-ebscohost-com.proxy.library.cornell.edu/login.aspx?direct=true&db=nlebk&AN=480968&site=ehost-live</ref>

	In (stochastic) gradient descent without momentum, the update rule at each iteration is given by:		In (stochastic) gradient descent without momentum, the update rule at each iteration is given by:

	~~''W = W -~~ <math>\~~alpha~~</math>~~dW''~~		<math>\theta_i=\theta_{i-1}-\gamma*g_i
			</math>

	Where:		Where:
	*''W'' denotes the parameters to the cost function		*''<math>\theta
	*''dW'' is the gradient indicating which direction to decrease the cost function by
	*''<math>\~~alpha~~</math>'' is the hyperparameter representing the learning rate<br />		</math>'' denotes the parameters to the cost function
			*''<math>g_i
			</math>'' is the gradient indicating which direction to decrease the cost function by
			*''<math>\gamma
			</math>'' is the hyperparameter representing the learning rate<br />
	In (stochastic) gradient descent with momentum, the update rule at each iteration is given by:		In (stochastic) gradient descent with momentum, the update rule at each iteration is given by:

	~~''V~~<math>~~dw</math>~~ = ~~βV<math>dw~~</math> ~~+ (1-β)dW''~~		<math>b_i=\mu*b_{i-1}+g_i
			</math>

	~~''W = W -''~~ <math>\~~alpha</math>''V<math>dw~~</math>''		<math>\theta_i=\theta_{i-1}-\gamma*b_i
			</math>

	Where:		Where:
	* ''β'' is a new hyperparameter that denotes the momentum constant
			*''<math>\theta

			</math>'' denotes the parameters to the cost function
			*''<math>g_i
			</math>'' is the gradient indicating which direction to decrease the cost function by
			*''<math>\gamma
			</math>'' is the hyperparameter representing the learning rate
			*<math>b_i
			</math> is the modified step direction term (as opposed to just using ''<math>g_i
			</math>'') that incorporates momentum

			*''<math>\mu
			</math>'' is a new hyperparameter that denotes the momentum constant


	Momentum can be applied to other gradient descent variations such as batch gradient descent and mini-batch gradient descent. Regardless of the gradient descent variation, the momentum hyperparameter ''β'' must be tuned in addition to the learning rate ~~hyper parameter~~ <math>\~~alpha~~</math>. ''β'' can be any value between 0 and 1. Generally, the larger the momentum value, the more past gradients must be taken into account, resulting in a smoother update. However, choosing a ''β'' value that is too large will result in over smoothing. It is also possible for a large ''β'' value to overshoot the target. As the ''β'' value gets closer to 0, momentum behaves similarly to steepest descent.<ref>Craven, M., & Page, D. (n.d.). ''Deep learning II: Momentum & Adaptive Step Size - UW–madison''. https://www.biostat.wisc.edu/~craven/cs760/lectures/DNNs-2.pdf</ref> A value of 0 is essentially gradient descent without momentum and a momentum value of 0.9 tends to be a good default choice.<ref name=":2" /> Finding the optimal ''β'' is a matter of trial and error to determine the best choice for a particular model such that the cost function is minimized.		Momentum can be applied to other gradient descent variations such as batch gradient descent and mini-batch gradient descent. Regardless of the gradient descent variation, the momentum hyperparameter ''<math>\mu
			</math>'' must be tuned in addition to the learning rate hyperparameter ''<math>\gamma
			</math>''. ''<math>\mu
			</math>'' can be any value between 0 and 1. Generally, the larger the momentum value, the more past gradients must be taken into account, resulting in a smoother update. However, choosing a ''<math>\mu
			</math>'' value that is too large will result in over smoothing. It is also possible for a large ''<math>\mu
			</math>'' value to overshoot the target. As the ''<math>\mu
			</math>'' value gets closer to 0, momentum behaves similarly to steepest descent.<ref>Craven, M., & Page, D. (n.d.). ''Deep learning II: Momentum & Adaptive Step Size - UW–madison''. https://www.biostat.wisc.edu/~craven/cs760/lectures/DNNs-2.pdf</ref> A value of 0 is essentially gradient descent without momentum and a momentum value of 0.9 tends to be a good default choice.<ref name=":2" /> Finding the optimal ''<math>\mu
			</math>'' is a matter of trial and error to determine the best choice for a particular model such that the cost function is minimized.

	=== Problems with Gradient Descent ===		=== Problems with Gradient Descent ===

Gg496: /* Theory, methodology, and/or algorithmic discussions */

2021-12-09T02:52:09Z

Theory, methodology, and/or algorithmic discussions

← Older revision		Revision as of 22:52, 8 December 2021
Line 28:		Line 28:


	Momentum can be applied to other gradient descent variations such as batch gradient descent and mini-batch gradient descent. Regardless of the gradient descent variation, the momentum hyperparameter ''β'' ~~will need to~~ be tuned in addition to the learning rate hyper parameter <math>\alpha</math>. ''β'' can be any value between 0 and 1. Generally, the larger the momentum value, the more ~~we take~~ past gradients into account~~. This results~~ in a smoother update. However, choosing a ''β'' value that is too large will result in over smoothing. ~~Sometimes,~~ a large ''β'' value ~~can even~~ overshoot the target. As the ''β'' value gets closer to 0, momentum behaves ~~more similar~~ to steepest descent.<ref>Craven, M., & Page, D. (n.d.). ''Deep learning II: Momentum & Adaptive Step Size - UW–madison''. https://www.biostat.wisc.edu/~craven/cs760/lectures/DNNs-2.pdf</ref> A value of 0 is essentially gradient descent without momentum and a momentum value of 0.9 tends to be a good default choice.<ref name=":2" /> Finding the optimal ''β'' is a matter of trial and error to ~~see what works~~ best for ~~your~~ model such that the cost function is minimized.		Momentum can be applied to other gradient descent variations such as batch gradient descent and mini-batch gradient descent. Regardless of the gradient descent variation, the momentum hyperparameter ''β'' must be tuned in addition to the learning rate hyper parameter <math>\alpha</math>. ''β'' can be any value between 0 and 1. Generally, the larger the momentum value, the more past gradients must be taken into account, resulting in a smoother update. However, choosing a ''β'' value that is too large will result in over smoothing. It is also possible for a large ''β'' value to overshoot the target. As the ''β'' value gets closer to 0, momentum behaves similarly to steepest descent.<ref>Craven, M., & Page, D. (n.d.). ''Deep learning II: Momentum & Adaptive Step Size - UW–madison''. https://www.biostat.wisc.edu/~craven/cs760/lectures/DNNs-2.pdf</ref> A value of 0 is essentially gradient descent without momentum and a momentum value of 0.9 tends to be a good default choice.<ref name=":2" /> Finding the optimal ''β'' is a matter of trial and error to determine the best choice for a particular model such that the cost function is minimized.

	=== Problems with Gradient Descent ===		=== Problems with Gradient Descent ===

Gg496: /* Applications */

2021-12-09T02:47:55Z

Applications

← Older revision		Revision as of 22:47, 8 December 2021
Line 210:		Line 210:
	== Applications ==		== Applications ==

	Momentum is widely used in the machine learning community for optimizing non-convex functions such as deep neural networks.<ref name=":2">Defazio, A. ''Momentum via primal averaging: Theoretical Insights and Learning Rate Schedules for Non-Convex Optimization''. https://arxiv.org/pdf/2010.00406.pdf</ref> Empirically, momentum methods outperform traditional stochastic gradient descent approaches.<ref name=":2" /> In deep learning, SGD is widely prevalent and is the underlying basis for many optimizers such as Adam, Adadelta, RMSProp, etc. which already utilize momentum.<ref>Rosebrock, A. (2021, May 7). ''Gradient descent algorithms and variations''. PyImageSearch. https://www.pyimagesearch.com/2021/05/05/gradient-descent-algorithms-and-variations/</ref> The momentum extension for optimization algorithms is available in many popular machine learning frameworks such as PyTorch, tensor flow, and scikit-learn. Generally, any problem that can be solved with stochastic gradient descent can benefit from the application of momentum. These are often unconstrained optimization problems~~, or in line with it's application to machine learning, such as model training~~. Some common SGD applications where momentum may be applied are ridge and logistic regression and support vector machines.<ref>Menon, A. (2009, February 27). ''Large-Scale Support Vector Machines: Algorithms and Theory''. https://cseweb.ucsd.edu//~akmenon/ResearchExamTalk.pdf</ref>		Momentum is widely used in the machine learning community for optimizing non-convex functions such as deep neural networks.<ref name=":2">Defazio, A. ''Momentum via primal averaging: Theoretical Insights and Learning Rate Schedules for Non-Convex Optimization''. https://arxiv.org/pdf/2010.00406.pdf</ref> Empirically, momentum methods outperform traditional stochastic gradient descent approaches.<ref name=":2" /> In deep learning, SGD is widely prevalent and is the underlying basis for many optimizers such as Adam, Adadelta, RMSProp, etc. which already utilize momentum to reduce computation speed.<ref>Rosebrock, A. (2021, May 7). ''Gradient descent algorithms and variations''. PyImageSearch. https://www.pyimagesearch.com/2021/05/05/gradient-descent-algorithms-and-variations/</ref> The momentum extension for optimization algorithms is available in many popular machine learning frameworks such as PyTorch, tensor flow, and scikit-learn. Generally, any problem that can be solved with stochastic gradient descent can benefit from the application of momentum. These are often unconstrained optimization problems. Some common SGD applications where momentum may be applied are ridge and logistic regression and support vector machines.<ref>Menon, A. (2009, February 27). ''Large-Scale Support Vector Machines: Algorithms and Theory''. https://cseweb.ucsd.edu//~akmenon/ResearchExamTalk.pdf</ref> Classification problems including those relating to cancer diagnosis<ref>Rehman, M. Z., & Nawi, N. M. (2011, June). The effect of adaptive momentum in improving the accuracy of gradient descent back propagation algorithm on classification problems. In ''International Conference on Software Engineering and Computer Systems'' (pp. 380-390). Springer, Berlin, Heidelberg.</ref> and image determination <ref>Zhang M., Smart W. (2004) Genetic Programming with Gradient Descent Search for Multiclass Object Classification. In: Keijzer M., O’Reilly UM., Lucas S., Costa E., Soule T. (eds) Genetic Programming. EuroGP 2004. Lecture Notes in Computer Science, vol 3003. Springer, Berlin, Heidelberg. <nowiki>https://doi.org/10.1007/978-3-540-24650-3_38</nowiki></ref> can also have reduced run times when momentum is implemented. In the case of medical diagnoses, this increased computation speed can directly benefit patients through faster diagnosis times and higher accuracy of diagnosis within the neural network.

	Momentum is also very useful in objective functions that have a large amount of curvature.<ref name=":0" /> These are areas where the gradients changes a lot. Since momentum leverages an exponential weighted average, smaller steps will be taken in these regions that have higher curvature resulting in dampened oscillations.		Momentum is also very useful in objective functions that have a large amount of curvature.<ref name=":0" /> These are areas where the gradients changes a lot. Since momentum leverages an exponential weighted average, smaller steps will be taken in these regions that have higher curvature resulting in dampened oscillations.

	Overall, momentum may have farther reaching applicability to accelerating second order methods and deeper connections to other methods, such as the ellipsoid algorithm.<ref>Goh, G. (2017, April 4). ''Why momentum really works''. Distill. https://distill.pub/2017/momentum/</ref>		Overall, momentum may have farther reaching applicability to accelerating second order methods and deeper connections to other methods, such as the ellipsoid algorithm.<ref>Goh, G. (2017, April 4). ''Why momentum really works''. Distill. https://distill.pub/2017/momentum/</ref>

	== Conclusion ==		== Conclusion ==

Gg496 at 02:05, 9 December 2021

2021-12-09T02:05:02Z

← Older revision		Revision as of 22:05, 8 December 2021
Line 210:		Line 210:
	== Applications ==		== Applications ==

	Momentum is widely used in the machine learning community for ~~training~~ non-convex ~~models~~ such as deep neural networks.<ref name=":2">Defazio, A. ''Momentum via primal averaging: Theoretical Insights and Learning Rate Schedules for Non-Convex Optimization''. https://arxiv.org/pdf/2010.00406.pdf</ref> Empirically, momentum methods outperform traditional stochastic gradient descent approaches.<ref name=":2" /> In deep learning, SGD is widely prevalent and is the underlying basis for many optimizers such as Adam, Adadelta, RMSProp, etc.<ref>Rosebrock, A. (2021, May 7). ''Gradient descent algorithms and variations''. PyImageSearch. https://www.pyimagesearch.com/2021/05/05/gradient-descent-algorithms-and-variations/</ref> The momentum extension for optimization algorithms is available in many popular machine learning frameworks such as PyTorch, tensor flow, and scikit-learn. Generally, any problem that can be solved with stochastic gradient descent can benefit from the application of momentum. These are often unconstrained optimization problems, or in line with it's application to machine learning, such as model training. Some common SGD applications where momentum may be applied are ridge and logistic regression and support vector machines.<ref>Menon, A. (2009, February 27). ''Large-Scale Support Vector Machines: Algorithms and Theory''. https://cseweb.ucsd.edu//~akmenon/ResearchExamTalk.pdf</ref>		Momentum is widely used in the machine learning community for optimizing non-convex functions such as deep neural networks.<ref name=":2">Defazio, A. ''Momentum via primal averaging: Theoretical Insights and Learning Rate Schedules for Non-Convex Optimization''. https://arxiv.org/pdf/2010.00406.pdf</ref> Empirically, momentum methods outperform traditional stochastic gradient descent approaches.<ref name=":2" /> In deep learning, SGD is widely prevalent and is the underlying basis for many optimizers such as Adam, Adadelta, RMSProp, etc. which already utilize momentum.<ref>Rosebrock, A. (2021, May 7). ''Gradient descent algorithms and variations''. PyImageSearch. https://www.pyimagesearch.com/2021/05/05/gradient-descent-algorithms-and-variations/</ref> The momentum extension for optimization algorithms is available in many popular machine learning frameworks such as PyTorch, tensor flow, and scikit-learn. Generally, any problem that can be solved with stochastic gradient descent can benefit from the application of momentum. These are often unconstrained optimization problems, or in line with it's application to machine learning, such as model training. Some common SGD applications where momentum may be applied are ridge and logistic regression and support vector machines.<ref>Menon, A. (2009, February 27). ''Large-Scale Support Vector Machines: Algorithms and Theory''. https://cseweb.ucsd.edu//~akmenon/ResearchExamTalk.pdf</ref>

	Momentum is also very useful in objective functions that have a large amount of curvature.<ref name=":0" /> These are areas where the gradients changes a lot. Since momentum leverages an exponential weighted average, smaller steps will be taken in these regions that have higher curvature resulting in dampened oscillations.		Momentum is also very useful in objective functions that have a large amount of curvature.<ref name=":0" /> These are areas where the gradients changes a lot. Since momentum leverages an exponential weighted average, smaller steps will be taken in these regions that have higher curvature resulting in dampened oscillations.

Eh672: /* Theory, methodology, and/or algorithmic discussions */

2021-12-09T00:34:02Z

Theory, methodology, and/or algorithmic discussions

← Older revision		Revision as of 20:34, 8 December 2021
Line 8:		Line 8:

	=== Algorithm ===		=== Algorithm ===
	The main idea behind momentum is to compute an exponentially weighted average of the gradients and use that to update the weights. By taking past gradients into account, the steps to gradient descent become smoothed out, which can reduce the amount of "zig zagging" seen in iterations (where the iterative solutions are going between above and below the true curve). <ref>Murphy~~, Kevin~~. ''Machine ~~Learning~~''. ~~<nowiki>~~https://~~eds-p~~-ebscohost-com.proxy.library.cornell.edu/~~eds/ebookviewer/ebook/bmxlYmtfXzQ4MDk2OF9fQU41~~?~~sid~~=~~d9abaf85-26da-4cc7-87fc-020b7509ddf7@redis~~&~~vid~~=0&~~format~~=EB&~~rid~~=~~1</nowiki>~~</ref>		The main idea behind momentum is to compute an exponentially weighted average of the gradients and use that to update the weights. By taking past gradients into account, the steps to gradient descent become smoothed out, which can reduce the amount of "zig zagging" seen in iterations (where the iterative solutions are going between above and below the true curve). <ref>Kevin P. Murphy. ''Machine Learning : A Probabilistic Perspective''. The MIT Press; 2012. https://search-ebscohost-com.proxy.library.cornell.edu/login.aspx?direct=true&db=nlebk&AN=480968&site=ehost-live</ref>

	In (stochastic) gradient descent without momentum, the update rule at each iteration is given by:		In (stochastic) gradient descent without momentum, the update rule at each iteration is given by:

Eh672: /* References */

2021-12-09T00:26:22Z

References

← Older revision		Revision as of 20:26, 8 December 2021
Line 2:		Line 2:

	== Introduction ==		== Introduction ==
	Momentum is an extension to the [https://optimization.cbe.cornell.edu/index.php?title=Stochastic_gradient_descent gradient descent] optimization algorithm that builds inertia in a search direction to overcome local minima and oscillation of noisy gradients.<ref name=":0">https://machinelearningmastery.com/gradient-descent-with-momentum-from-scratch/</ref> It is based on the same concept of momentum in physics. A classical example of the concept is a ball rolling down a hill that gathers enough momentum to overcome a plateau region and make it to a global minima instead of getting stuck at a local minima. Momentum adds history to the parameter updates of descent problems which significantly accelerates the optimization process. The amount of history included in the update equation is determined via a hyperparameter.<ref name=":0" /> This hyperparameter is a value ranging from 0 to 1, where a momentum value of 0 is equivalent to gradient descent without momentum.<ref name=":0" /> A higher momentum value means more gradients from the past (history) are considered.<ref name=":1">https://towardsdatascience.com/gradient-descent-with-momentum-59420f626c8f</ref>		Momentum is an extension to the [https://optimization.cbe.cornell.edu/index.php?title=Stochastic_gradient_descent gradient descent] optimization algorithm that builds inertia in a search direction to overcome local minima and oscillation of noisy gradients.<ref name=":0">Brownlee, J. (2021, October 11). ''Gradient descent with momentum from scratch''. Machine Learning Mastery. https://machinelearningmastery.com/gradient-descent-with-momentum-from-scratch/.</ref> It is based on the same concept of momentum in physics. A classical example of the concept is a ball rolling down a hill that gathers enough momentum to overcome a plateau region and make it to a global minima instead of getting stuck at a local minima. Momentum adds history to the parameter updates of descent problems which significantly accelerates the optimization process. The amount of history included in the update equation is determined via a hyperparameter.<ref name=":0" /> This hyperparameter is a value ranging from 0 to 1, where a momentum value of 0 is equivalent to gradient descent without momentum.<ref name=":0" /> A higher momentum value means more gradients from the past (history) are considered.<ref name=":1">Bhat, R. (2020, October 22). ''Gradient descent with momentum''. Medium. https://towardsdatascience.com/gradient-descent-with-momentum-59420f626c8f</ref>

	Gradient descent also has several limitations which can be addressed using momentum application, including issues with noise in the oscillations and potential failure to solve due to non-convex functions having multiple local minima.<ref name=":4">J. Sum, C. -S. Leung and K. Ho, "A Limitation of Gradient Descent Learning," in IEEE Transactions on Neural Networks and Learning Systems, vol. 31, no. 6, pp. 2227-2232, June 2020, doi: 10.1109/TNNLS.2019.2927689.</ref><ref name=":1" /> Momentum addresses these limitations using exponentially weighted gradients, avoiding errors caused by iterations being equally weighted.		Gradient descent also has several limitations which can be addressed using momentum application, including issues with noise in the oscillations and potential failure to solve due to non-convex functions having multiple local minima.<ref name=":4">J. Sum, C. -S. Leung and K. Ho, "A Limitation of Gradient Descent Learning," in IEEE Transactions on Neural Networks and Learning Systems, vol. 31, no. 6, pp. 2227-2232, June 2020, doi: 10.1109/TNNLS.2019.2927689.</ref><ref name=":1" /> Momentum addresses these limitations using exponentially weighted gradients, avoiding errors caused by iterations being equally weighted.
Line 28:		Line 28:


	Momentum can be applied to other gradient descent variations such as batch gradient descent and mini-batch gradient descent. Regardless of the gradient descent variation, the momentum hyperparameter ''β'' will need to be tuned in addition to the learning rate hyper parameter <math>\alpha</math>. ''β'' can be any value between 0 and 1. Generally, the larger the momentum value, the more we take past gradients into account. This results in a smoother update. However, choosing a ''β'' value that is too large will result in over smoothing. Sometimes, a large ''β'' value can even overshoot the target. As the ''β'' value gets closer to 0, momentum behaves more similar to steepest descent.<ref>https://www.biostat.wisc.edu/~craven/cs760/lectures/DNNs-2.pdf</ref> A value of 0 is essentially gradient descent without momentum and a momentum value of 0.9 tends to be a good default choice.<ref name=":2" /> Finding the optimal ''β'' is a matter of trial and error to see what works best for your model such that the cost function is minimized.		Momentum can be applied to other gradient descent variations such as batch gradient descent and mini-batch gradient descent. Regardless of the gradient descent variation, the momentum hyperparameter ''β'' will need to be tuned in addition to the learning rate hyper parameter <math>\alpha</math>. ''β'' can be any value between 0 and 1. Generally, the larger the momentum value, the more we take past gradients into account. This results in a smoother update. However, choosing a ''β'' value that is too large will result in over smoothing. Sometimes, a large ''β'' value can even overshoot the target. As the ''β'' value gets closer to 0, momentum behaves more similar to steepest descent.<ref>Craven, M., & Page, D. (n.d.). ''Deep learning II: Momentum & Adaptive Step Size - UW–madison''. https://www.biostat.wisc.edu/~craven/cs760/lectures/DNNs-2.pdf</ref> A value of 0 is essentially gradient descent without momentum and a momentum value of 0.9 tends to be a good default choice.<ref name=":2" /> Finding the optimal ''β'' is a matter of trial and error to see what works best for your model such that the cost function is minimized.

	=== Problems with Gradient Descent ===		=== Problems with Gradient Descent ===
	With gradient descent, a weight update at time ''t'' is given by the learning rate and gradient at that exact moment.<ref name=":1" /> This means that the previous steps are not considered when searching for the next iteration's solution.		With gradient descent, a weight update at time ''t'' is given by the learning rate and gradient at that exact moment.<ref name=":1" /> This means that the previous steps are not considered when searching for the next iteration's solution.
	[[File:Gradient descent momentum.png\|thumb\|Gradient descent with and without momentum.<ref name=":3">https://cedar.buffalo.edu/~srihari/CSE676/8.3%20BasicOptimizn.pdf</ref>]]		[[File:Gradient descent momentum.png\|thumb\|Gradient descent with and without momentum.<ref name=":3">Srihari, S. (n.d.). ''Basic Optimization Algorithms''. Deep learning.https://cedar.buffalo.edu/~srihari/CSE676/8.3%20BasicOptimizn.pdf</ref>]]
	This results in two issues:		This results in two issues:

Line 210:		Line 210:
	== Applications ==		== Applications ==

	Momentum is widely used in the machine learning community for training non-convex models such as deep neural networks.<ref name=":2">https://arxiv.org/pdf/2010.00406.pdf</ref> Empirically, momentum methods outperform traditional stochastic gradient descent approaches.<ref name=":2" /> In deep learning, SGD is widely prevalent and is the underlying basis for many optimizers such as Adam, Adadelta, RMSProp, etc.<ref>https://www.pyimagesearch.com/2021/05/05/gradient-descent-algorithms-and-variations/</ref> The momentum extension for optimization algorithms is available in many popular machine learning frameworks such as PyTorch, tensor flow, and scikit-learn. Generally, any problem that can be solved with stochastic gradient descent can benefit from the application of momentum. These are often unconstrained optimization problems, or in line with it's application to machine learning, such as model training. Some common SGD applications where momentum may be applied are ridge and logistic regression and support vector machines.<ref>https://cseweb.ucsd.edu//~akmenon/ResearchExamTalk.pdf</ref>		Momentum is widely used in the machine learning community for training non-convex models such as deep neural networks.<ref name=":2">Defazio, A. ''Momentum via primal averaging: Theoretical Insights and Learning Rate Schedules for Non-Convex Optimization''. https://arxiv.org/pdf/2010.00406.pdf</ref> Empirically, momentum methods outperform traditional stochastic gradient descent approaches.<ref name=":2" /> In deep learning, SGD is widely prevalent and is the underlying basis for many optimizers such as Adam, Adadelta, RMSProp, etc.<ref>Rosebrock, A. (2021, May 7). ''Gradient descent algorithms and variations''. PyImageSearch. https://www.pyimagesearch.com/2021/05/05/gradient-descent-algorithms-and-variations/</ref> The momentum extension for optimization algorithms is available in many popular machine learning frameworks such as PyTorch, tensor flow, and scikit-learn. Generally, any problem that can be solved with stochastic gradient descent can benefit from the application of momentum. These are often unconstrained optimization problems, or in line with it's application to machine learning, such as model training. Some common SGD applications where momentum may be applied are ridge and logistic regression and support vector machines.<ref>Menon, A. (2009, February 27). ''Large-Scale Support Vector Machines: Algorithms and Theory''. https://cseweb.ucsd.edu//~akmenon/ResearchExamTalk.pdf</ref>

	Momentum is also very useful in objective functions that have a large amount of curvature.<ref name=":0" /> These are areas where the gradients changes a lot. Since momentum leverages an exponential weighted average, smaller steps will be taken in these regions that have higher curvature resulting in dampened oscillations.		Momentum is also very useful in objective functions that have a large amount of curvature.<ref name=":0" /> These are areas where the gradients changes a lot. Since momentum leverages an exponential weighted average, smaller steps will be taken in these regions that have higher curvature resulting in dampened oscillations.

	Overall, momentum may have farther reaching applicability to accelerating second order methods and deeper connections to other methods, such as the ellipsoid algorithm.<ref>https://distill.pub/2017/momentum/</ref>		Overall, momentum may have farther reaching applicability to accelerating second order methods and deeper connections to other methods, such as the ellipsoid algorithm.<ref>Goh, G. (2017, April 4). ''Why momentum really works''. Distill. https://distill.pub/2017/momentum/</ref>

	== Conclusion ==		== Conclusion ==

Eh672: /* SGD without Momentum */

2021-12-09T00:05:09Z

SGD without Momentum

← Older revision		Revision as of 20:05, 8 December 2021
Line 52:		Line 52:
	</math>. This example uses python to construct a loss function and optimizer with PyTorch.<ref>PyTorch Tutorials. https://pytorch.org/tutorials/beginner/basics/optimization_tutorial.html</ref> The solver iterates through the following equations:		</math>. This example uses python to construct a loss function and optimizer with PyTorch.<ref>PyTorch Tutorials. https://pytorch.org/tutorials/beginner/basics/optimization_tutorial.html</ref> The solver iterates through the following equations:

	<math>g_i = \nabla\theta_i f_i (\theta_{i-1}) = 1.2\theta_{i-1}^3 - 0.3\theta_{i-1}^2 - 4*\theta_{i-1} - 0.8)		<math>g_i = \nabla\theta_i f_i (\theta_{i-1}) = 1.2\theta_{i-1}^3 - 0.3\theta_{i-1}^2 - 4*\theta_{i-1} - 0.8

	</math>		</math>
Line 125:		Line 125:
	</math>. The solver iterates through the following equations:		</math>. The solver iterates through the following equations:

	<math>g_i = \nabla\theta_i f_i (\theta_{i-1}) = 1.2\theta_{i-1}^3 - 0.3\theta_{i-1}^2 - 4*\theta_{i-1} - 0.8)		<math>g_i = \nabla\theta_i f_i (\theta_{i-1}) = 1.2\theta_{i-1}^3 - 0.3\theta_{i-1}^2 - 4*\theta_{i-1} - 0.8

	</math>		</math>
Line 170:		Line 170:
	</math> and <math>y		</math> and <math>y
	</math> for each iteration after starting at <math>\theta_0=-2.8		</math> for each iteration after starting at <math>\theta_0=-2.8
	</math>.		</math>. Using momentum, this solver gives the correct solution for the global minimum at <math>x=2.04
			</math> and <math>y=-5.61
			</math>, as shown in the graph.
	{\| class="wikitable"		{\| class="wikitable"
	\|+		\|+
Line 205:		Line 207:
	\|<nowiki>-5.608</nowiki>		\|<nowiki>-5.608</nowiki>
	\|}		\|}
	~~Using momentum, this solver gives the correct solution for the global minimum at <math>x=2.04~~
	~~</math> and <math>y=-5.61~~
	~~</math>, as shown in the graph.~~
	== Applications ==		== Applications ==