I am trying to understand how gradient descent works. My understanding is that the update rule works as follows: $$x_{n+1} = x_n - \alpha f'(x_n)$$ This seems magical to me.

1. How did this update rule come about?
2. How do I know $x_{n+1}$ lies on $f(x)$?

A simple explanation will be appreciated. Simple proof and/or pictorial description would be nice too!

One important property of the gradient of a function is that it points in the direction where the function increases most if you take an infinitely small step. Conversely, it decreases most in the exact opposite of the direction. Thus, moving a small step in that direction will increase $f$.

It is best to work through this with an example to see that it works. Say we want to minimize $f(x) = x^2$. The minimum is at $x = 0$ and we start our optimization at $x_0 = 2$. The derivative is given by $f'(x) = 2x$. Thus, the gradient at our starting position is $f'(x_0) = 4$. Moving into the opposite direction of that gradient (since we are minimizing) brings us towards 0.

Of course, there are issues: Finding a good step rate (your $\alpha$) is crucial, since you might overshoot. Also, gradient descent might take very long in high dimensions. This is why optimization is still a very active and important branch of mathematics.

Regarding your second question: gradient descent assumes that all $x$ are in the domain of $f$.

You might find further guidance on math.stackexchange.com.

• Thank you for your answer. But how do I know that $x_{n+1}$ lies on $f(x)$, as I decrease $x_n$ by a certain value? Is that simply an assumption?? – Jimmy Nov 12 '12 at 21:26
• $x_{n+1}$ isn't on $f(x)$, it's the input to $f(x)$. $f(x_{n+1})$ is on $f(x)$. – Max Nov 12 '12 at 21:31
• @Max Maybe I am missing something. If $x_{n+1}$ is not on $f(x)$, how are we able to evaluate the function at that point? – Jimmy Nov 12 '12 at 22:14
• I think the poster's question has to do with the dynamical system aspect of it. If $f(x_n)$ takes $x_{n+1}$ to a boundary of the system's compact domain, then what happens since $f'(x_{n+1})$ is singular? This is an issue with any iterative solver, though, and is more than just a matter of supplying better starting values. Statisticians often look to a change of variable to ensure that $x$ has a sane domain, such as GLMs and Newton-Raphson where the model is linear and regular on the log odds scale rather than irregular on the probability scale. – AdamO Nov 12 '12 at 22:16
• Can you explain more of what nature $f(x)$ exactly is? In most optimization problems, $f: \mathbb{R}^n \rightarrow \mathbb{R}$, so going along the gradient always keeps you in the domain. – bayerj Nov 13 '12 at 7:45