Convex and non-convex: valleys, traps and plateaus

A convex loss has one valley and gradient descent finds it. Network losses have many valleys, saddles and flat stretches, and where you start decides where you end.

10 min Prerequisites: Lesson 28 (learning rates)

Symbols in this lessonH Hessian ∇ nabla / gradient argmin arg min / arg max

1. The idea

A function is convex if the straight line between any two points on its graph never dips below the graph: a single bowl. For a convex loss every local minimum is the global one, and gradient descent with a sensible step size finds it from anywhere. Linear and logistic regression have convex losses.

Neural network losses are not convex. They can have several valleys, and where gradient descent ends up depends on where it starts. They also have saddle points, which slope down in some directions and up in others, and wide flat plateaus where the gradient is so small that progress nearly stops.

In practice it is kinder than it sounds. In very high dimensions most places with zero gradient are saddles rather than bad minima, the noise in mini-batch gradients helps to escape them, and many different minima give networks that work about equally well.

2. Try it: where do you end up?

Pick a shape and a starting θ, and gradient descent takes 60 steps. On the two-valley loss, find the starting points that end in the shallower valley. On the plateau, see how little a far start moves.

3. The math

Convexity

f\big(t\,a + (1 - t)\,b\big) \le t\,f(a) + (1 - t)\,f(b), \qquad 0 \le t \le 1

The chord between any two points lies on or above the graph.

Flat isn't always best

\nabla f(\theta) = \mathbf{0} \;\not\Rightarrow\; f(\theta) = \min f

A zero gradient can be a local minimum, a maximum or a saddle.

The second-derivative test (1-D)

f''(\theta) > 0 \text{ at a minimum}, \qquad f''(\theta) < 0 \text{ at a maximum}

In many dimensions: the signs of the Hessian's eigenvalues.

A saddle

f(x, y) = x^2 - y^2, \qquad \nabla f(0, 0) = \mathbf{0}

Up along x, down along y.

The widget's two valleys

L(\theta) = 0.05\,\theta^4 - 0.6\,\theta^2 + 0.3\,\theta + 2

The left valley is deeper than the right.

4. The code (python)

mm6_nonconvex.py

def L(t):
    return 0.05 * t**4 - 0.6 * t**2 + 0.3 * t + 2

def dL(t):
    return 0.2 * t**3 - 1.2 * t + 0.3

def descend(t, eta=0.1, steps=200):
    for _ in range(steps):
        t = t - eta * dL(t)
    return t

ends = [round(descend(start), 3) for start in (2.5, 0.5, -0.5, -3.0)]
print(ends)                              # [2.313, 2.313, -2.566, -2.566]
print([round(L(t), 3) for t in ends])    # [0.915, 0.915, -0.553, -0.553]

5. You’ll see this in

Module 4: Jacobians and Hessians curvature tells minima from saddles
Core Course chapter 13: initialization and normalization where you start matters
Reference notes: convexity, optimization and duality

6. Check yourself

Answer all 4 questions correctly to complete the chapter · 0 / 4 done

Q1/4 What is special about the minima of a convex function?

Q2/4 On a non-convex loss, where does gradient descent end up?

Q3/4 What is a saddle point?

Q4/4 Why are plateaus a problem for gradient descent?

Finished this chapter?

Weekly newsletter

What changed in ML architectures this week

New models worth knowing, benchmark moves, and one architecture explained in plain words. Free, once a week, unsubscribe anytime.

Learn machine learning from scratch