When does gradient descent get stuck?
Gradient descent finds a low point, but not always the lowest one. It can settle in a local minimum, crawl across flat ground, or fly off to infinity.
In this lesson you will use the optimiser in SciPy, a Python library for numerical work. You will see each way descent can fail and how to tell which has happened.
By the end of this lesson
Note
I can use SciPy's optimiser and say when descent gets stuck.
Key words
| Word | What it means |
|---|---|
| Optimiser | a program that searches for the best input |
| Local minimum | a low point with higher ground on both sides |
| Global minimum | the lowest point of the whole function |
| Plateau | flat ground where the slope is almost zero |
| Starting point | the value of x where the search begins |
The cells students fill in are left blank in this preview.
SciPy has a ready-made minimiser
You do not always have to write the loop. The function minimize in scipy.optimize takes a function and a starting point, then picks its own steps and stopping rule.
Your function takes one list of inputs, so x is p[0]. The result has .x, the best input found, and .fun, the value there. The lab's image already holds SciPy.
Minimise (x - 3) squared + 1
docker exec jupyter python3 -c "from scipy.optimize import minimize; r = minimize(lambda p: (p[0] - 3) ** 2 + 1, [0.0]); print(round(r.x[0], 3), round(r.fun, 3))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
The starting point can decide the answer
The curve x ** 4 - 3 * x ** 2 + x has two valleys. The left one is deeper. Each valley is a local minimum, and the lowest of them is the global minimum.
A downhill walk ends in whichever valley it starts above. Start at -2 and it ends in the deep valley. Start at 2 and it ends in the shallow one.
Worked example: two valleys, two answers
| Start | Slope at the start | Which way it goes | Ends at x | Height there |
|---|---|---|---|---|
| -2 | -19 (falling) | Right | -1.301 | -3.514 |
| 2 | 21 (rising) | Left | 1.131 | -1.07 |
The cells students fill in are left blank in this preview.
Let SciPy start in both places
docker exec jupyter python3 -c "from scipy.optimize import minimize; f = lambda p: p[0] ** 4 - 3 * p[0] ** 2 + p[0]; print(round(minimize(f, [-2.0]).x[0], 3), round(minimize(f, [2.0]).x[0], 3))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people think gradient descent always finds the lowest point. It finds a low point near where it started. To look further, run it from several starting points and keep the answer with the lowest height.
Try four starting points
# Plain descent on x ** 4 - 3 * x ** 2 + x, from four starting points.
def slope(x):
return 4 * x ** 3 - 6 * x + 1
def height(x):
return x ** 4 - 3 * x ** 2 + x
for start in [-2.0, 0.16, 0.18, 2.0]:
x = start
for step in range(500):
x = x - 0.01 * slope(x)
print(start, round(x, 3), round(height(x), 3))
# Which starts reach the lower valley?
# Try a start of 0.17 and say which valley it picks.
Flat ground and big steps are traps
On a plateau the slope is nearly zero, so each step is tiny and the loop crawls or stops far from any minimum. A step limit keeps it from running for ever.
A rate that is too big does the opposite and diverges. To tell what happened, look at the path of x values. If it grows without bound it diverged. If the slope is near zero it settled. If neither, it is still moving.
Worked example: reading what happened
| What you see | The last slope | Verdict |
|---|---|---|
| x settles on one value | Close to zero | Converged |
| x flips sign and gets larger every step | Growing | Diverged |
| x moves slowly and the limit is reached | Small but not zero | Still moving, so run longer or raise the rate |
| x bounces between two values | Not shrinking | Still moving, so lower the rate |
The cells students fill in are left blank in this preview.
Going further
In your own notebook, ask minimize for the minimum of x ** 4 - 3 * x ** 2 + x from a start of 0.0.
The slope at 0 is 1, so predict which valley it picks. Then try 0.17 and 0.16 and see whether the answer changes.