Description
Gradient descent is based on the observation that if the multivariable function is defined and differentiable in a neighborhood of a point, then decreases fastest if one goes from in the direction of the negative gradient of at, . It follows that, if
for a small enough number, then . With this observation in mind, one starts with a guess for a local minimum of, and considers the sequence such that
We have
so hopefully the sequence converges to the desired local minimum. Note that the value of the step size is allowed to change at every iteration. With certain assumptions on the function (for example, convex and Lipschitz) and particular choices of (e.g., chosen via a line search that satisfies the Wolfe conditions), convergence to a local minimum can be guaranteed. When the function is convex, all local minima are also global minima, so in this case gradient descent can converge to the global solution.
This process is illustrated in the picture to the right. Here is assumed to be defined on the plane, and that its graph has a bowl shape. The blue curves are the contour lines, that is, the regions on which the value of is constant. A red arrow originating at a point shows the direction of the negative gradient at that point. Note that the (negative) gradient at a point is orthogonal to the contour line going through that point. We see that gradient descent leads us to the bottom of the bowl, that is, to the point where the value of the function is minimal.
Read more about this topic: Gradient Descent
Famous quotes containing the word description:
“It is possible—indeed possible even according to the old conception of logic—to give in advance a description of all ‘true’ logical propositions. Hence there can never be surprises in logic.”
—Ludwig Wittgenstein (1889–1951)
“I was here first introduced to Joe.... He was a good-looking Indian, twenty-four years old, apparently of unmixed blood, short and stout, with a broad face and reddish complexion, and eyes, methinks, narrower and more turned up at the outer corners than ours, answering to the description of his race. Besides his underclothing, he wore a red flannel shirt, woolen pants, and a black Kossuth hat, the ordinary dress of the lumberman, and, to a considerable extent, of the Penobscot Indian.”
—Henry David Thoreau (1817–1862)
“The Sage of Toronto ... spent several decades marveling at the numerous freedoms created by a “global village” instantly and effortlessly accessible to all. Villages, unlike towns, have always been ruled by conformism, isolation, petty surveillance, boredom and repetitive malicious gossip about the same families. Which is a precise enough description of the global spectacle’s present vulgarity.”
—Guy Debord (b. 1931)