One slider turns a bowl into a mountain range. Watch gradient descent succeed, then watch the same algorithm get stuck.
Overview
The definition
A function is convex if, for any two points on it, the straight line joining them lies on or above the curve. A bowl is convex. A mountain range is not.
The equal statement in calculus: the second deriv is non-minus all over. In many dims, the Hessian is positive semi-definite — all its eigenvals at least zero.
Convexity and Optimisation Landscapes
This module needs JavaScript: the
numbers are computed in the page rather than recorded.
Worth knowing
A function is convex if the straight line between any two points on it never dips below the curve.
Convex means every local minimum is the global minimum. There is nowhere to get stuck.
Set bumpiness to zero and every starting point finds the same answer. Raise it and the starting point decides.
Neural network losses are wildly non-convex, and train well anyway — which needed explaining, and largely has been.
Convexity and Optimisation Landscapes
The property that makes optimisation easy, what happens without it. Why deep learning works even so.
Why it matters so much
One consequence carries the entire subject: in a convex function, each local min is the global min.
If you find a point where the grad is zero and the curvature is plus, you're done. Not "probably done" — done, with a proof.
Set the bumpiness control to zero and try each starting point on the slider. each one settles to the same place. The init doesn't matter, the run is reproducible, and there's a ensure at the end of it.
Now raise bumpiness. The curve grows local minima, and the starting point starts deciding the answer. Move the start slider at a fixed bumpiness and watch the final spot jump between basins — same function, same method, same learning rate, different answer.
What convexity buys, concretely
Ensured settling to the global optimum, with known rates.
Reproducibility. No dependence on init or on the order the data arrived in.
Certificates. You can prove a answer is best rather than hoping.
Solid stopping. A small grad really does mean you've arrived.
This is why linear regression, logistic regression, SVMs with convex loss, ridge and lasso are all so well behaved. Their goals are convex, and the solvers come with theory rather than folklore.
And yet deep learning works
Neural network losses are about as non-convex as functions get: millions of dims, vast numbers of stationary points, no ensures at all. By the arg above, training should be a lottery.
It isn't, and the explanation that emerged is worth knowing.
Saddle points, not local minima, dominate. In high dims, a stationary point needs *each* eigenval of the Hessian to be plus to be a local min. With millions of dims that is vanishingly unlikely. Almost each stationary point has some minus direction, making it a saddle. Saddles are escapable — the grad points away along the minus direction, and noise from mini-batching helps you find it.
The minima that exist are mostly similar. Empirically, the many minima of a large network reach close loss. Which one you land in matters less than that you landed.
Overparameterisation flattens the landscape. Wider networks have more paths down, and the loss surface turns easier rather than harder as room grows — which is the opposite of the intuition.
The learning rate
The third control shows a separate failure that is often blamed on non-convexity.
Turn the learning rate up with bumpiness at zero. A just right convex bowl — and descent still misbehaves, bouncing between the walls or diverging fully. Convexity ensures a unique min exists. It doesn't ensure your step size will find it.
The safe step depends on curvature, which is what the Hessian measures and what adaptive tuners guess.
The chord test, on numbers
Convexity has a meaning you can check by hand: the straight line between any two points on the curve must lie on or above it. Take f(x) = x² and the points at x = −2 and x = 4.
The chord's height at the midpoint is the mean of the endpoint values: (f(−2) + f(4)) / 2 = (4 + 16)/2 = 10. The curve's height at that same midpoint, x = 1, is f(1) = 1.
at the midpoint x = 1
value
the chord
10
the curve
1
The chord sits above the curve, by 9. It does so for *each* pair of points you pick — that is what makes x² convex, and why a single downhill walk finds its one min. Now try the same on f(x) = 0.15x² + 3sin(2x): between two well-chosen points the chord dips *below* the curve, because the ripples bulge upward past the straight line. One such dip is enough to disqualify convexity, and it's just the bulge a descent path can get stuck behind. The test isn't a metaphor. It's an inequality you can test at any two points.
The consequence is the one that separates the well-behaved models from the rest. Because x²-shaped goals pass the chord test all over, linear regression, logistic regression and SVMs with convex loss have a single min that each downhill path reaches. The answer doesn't depend on where you start. The rippled function fails the test a place, and that single failure is enough to trap a descent path in a basin that depends fully on its starting point, which is why a neural network gives a different answer on each restart.
And yet deep networks train anyway, because in millions of dims almost each stationary point is a saddle rather than a trap — a genuine min needs each Hessian eigenval plus at once. This Is vanishingly unlikely — and mini-batch noise slides the tuner off the saddles it meets.
Where it goes wrong with Convexity and Optimisation Landscapes
given a convex loss makes the whole problem convex. Squared error is convex in the guesses and non-convex in the weights of a network. What matters is convexity in the params being optimised.
Blaming non-convexity for a divergent run. Check the learning rate first; it's often that.
Running once and trusting the result on a non-convex problem. a few starts, or a schedule with restarts, is the min diligence.
Expecting convex theory to transfer. Settling rates for convex problems say nothing about a deep network.
Questions people ask about Convexity and Optimisation Landscapes
What is a convex function? One where the line segment between any two points on its graph lies on or above the graph. A bowl is convex and a double hump is not.
Why does convexity matter? Every local minimum of a convex function is a global minimum. Gradient descent with a sensible step size cannot get stuck.
How do I check convexity? For a twice-differentiable function, check that the Hessian is positive semi-definite everywhere. In one dimension, check that the second derivative is not negative.
Is a neural network loss convex? No, it has many saddle points and local minima. Training works anyway because the minima found in practice tend to be nearly as good as each other.
What is the effect of the learning rate? Too small and progress crawls, too large and the iterates overshoot or diverge. On a quadratic, anything above twice the inverse of the largest curvature diverges.
Are convex problems always easy? They are reliably solvable, but size still matters. Convex problems with huge data need stochastic or specialised methods.
One function gradient descent cannot fail on, and one it can
The same tuner, the same settings, run from many starting points on a convex function and then on a bumpy one. Convexity is the property that makes the starting point irrelevant.
example_01.pyNumPy
import numpy as np
def descend(f, grad, x0, lr=0.05, steps=2000):
x = float(x0)
for _ in range(steps):
x -= lr * grad(x)
return x
# convex: one bowl
f1 = lambda x: (x - 3.0) ** 2 + 2.0
grad1 = lambda x: 2 * (x - 3.0)
# non-convex: a bowl with ripples
f2 = lambda x: 0.15 * (x - 3.0) ** 2 + 3.0 * np.sin(2.0 * x)
grad2 = lambda x: 0.30 * (x - 3.0) + 6.0 * np.cos(2.0 * x)
starts = [-10.0, -5.0, -1.0, 0.0, 2.0, 6.0, 11.0]
print("convex f(x) = (x-3)^2 + 2")
for s in starts:
x = descend(f1, grad1, s)
print(" start %6.1f -> x %8.4f f %9.4f" % (s, x, f1(x)))
print(" every start lands in the same place.")
print()
print("non-convex f(x) = 0.15(x-3)^2 + 3 sin(2x)")
found = []
for s in starts:
x = descend(f2, grad2, s)
found.append(round(x, 3))
print(" start %6.1f -> x %8.4f f %9.4f" % (s, x, f2(x)))
best = min(found, key=lambda x: f2(x))
print(" %d distinct minima. best f=%.4f at x=%.3f" % (len(set(found)), f2(best), best))
print()
print("convex: one minimum, every path finds it. non-convex: many.")
print("test: the chord between any two points never dips below the curve.")
mids = np.linspace(0.05, 0.95, 19)
for fn, name in ((f1, "convex"), (f2, "non-convex")):
chord = [(1-t)*fn(-2)+t*fn(8) for t in mids]
curve = [fn((1-t)*-2+t*8) for t in mids]
viol = sum(c < v-1e-9 for c, v in zip(chord, curve))
print(" %-11s chord below curve at %d of %d points" % (name, viol, len(mids)))
Output
Check yourself
0 of 3
Answer without scrolling back up.
What is the defining consequence of convexity for optimisation?
Find a stationary point with positive curvature and you are done, with a proof. That is why linear and logistic regression are so well behaved.
Why are saddle points more common than local minima in high dimensions?
Almost every stationary point has some negative direction, making it escapable - and mini-batch noise helps find that direction.
Descent diverges on a perfectly convex bowl. What is the likely cause?
Convexity guarantees a unique minimum exists; it says nothing about whether your step size will find it. The safe step depends on curvature.
Cheat sheet
Convexity and Optimisation Landscapes
See why a convex loss surface has one minimum and gradient descent always finds it. Then watch what happens when convexity disappears.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.