Extensions
Gradient descent can be extended to handle constraints by including a projection onto the set of constraints. This method is only feasible when the projection is efficiently computable on a computer. Under suitable assumptions, this method converges. This method is a specific case of the forward-backward algorithm for monotone inclusions (which includes convex programming and variational inequalities).
Another extension of gradient descent is due to Yurii Nesterov from 1983, and has been subsequently generalized. He provides a simple modification of the algorithm that enables faster convergence for convex problems. Specifically, if the function is convex and is Lipschitz, and it is not assumed that is strongly convex, then the error in the objective value generated at each step by the gradient descent method will be bounded by . Using the Nesterov acceleration technique, the error decreases at . The method is remarkable since it requires essentially no extra heavy computation, yet yields faster convergence.
Read more about this topic: Gradient Descent
Famous quotes containing the word extensions:
“The psychological umbilical cord is more difficult to cut than the real one. We experience our children as extensions of ourselves, and we feel as though their behavior is an expression of something within us...instead of an expression of something in them. We see in our children our own reflection, and when we don’t like what we see, we feel angry at the reflection.”
—Elaine Heffner (20th century)
“If we focus exclusively on teaching our children to read, write, spell, and count in their first years of life, we turn our homes into extensions of school and turn bringing up a child into an exercise in curriculum development. We should be parents first and teachers of academic skills second.”
—Neil Kurshan (20th century)