Gradient Descent

Gradient Descent

Also known as steepest descent, or the method of steepest descent. It will help us find local minimum for cost function
Idea: start somewhere, keep changing to reduce cost function

Gradient Descent Algorithm:

Key concepts:

• Repeat until convergence, a threshold we decide to stop the algorithm ;)
• $\alpha$ = learning rate, how big of a step we take down hill in above image
• Simultaneously update $a_0$ and $a_1$

Here is an example where if you don't do simultaneous update, your algorithm will fail and/or output different result:

Let $J(a_0, a_1) = a_0a_1$, starting point $a_0, a_1 = (0, 1)$, learning rate $\alpha = 1$
then $J^{'}(a_0) = a_1$ and $J^{'}(a_1) = a_0$

Correct simultaneous update:
$temp_0 := a_0 - 1 * a_1 = 0 - 1 * 1 = -1$
$temp_1 := a_1 - 1 * a_0 = 0 - 1 * 0 = 0$
$a_0 = temp_0 = -1$
$a_1 = temp_1 = 0$

Incorrect not simultaneous update:
$temp_0 := a_0 - 1 * a_1 = 0 - 1 * 1 = -1$
$a_0 = temp_0 = -1$
$temp_1 := a_1 - 1 * a_0 = 0 - 1 * -1 = 1$
$a_1 = temp_1 = 1$

As you can see, values of $a_1$ are not the same even after just one iteration

Resources:

- So when is convergence? http://stackoverflow.com/questions/17289082/gradient-descent-convergence-how-to-decide-convergence

- https://www.coursera.org/learn/machine-learning/lecture/8SpIM/gradient-descent