Basic question about gradient descent 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. 


*

*How did this update rule come about? 

*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! 
 A: 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.
