ENID
Lensa ML

Convexity, Minima & Saddle Points

Step 1 of 6: Convex vs Non-Convex

Why shape matters for optimization

xf(x)Convex (bowl shape)
ConvexWaviness: 0.00Wavy
Local Minima
1
Is Convex?
Yes
Global Min
0.00

A convex function curves upward everywhere, forming a single bowl. Any local minimum is the global minimum, so downhill steps always find it.

Drag the Waviness slider from Convex toward Wavy. The curve is x² + t·1.8·sin(2.5x), and its second derivative is 2 − 11.25·t·sin(2.5x). That stays non-negative only while t is below about 0.18, so even a small wavy term breaks convexity. The formal definition is f(λa + (1−λ)b) ≤ λf(a) + (1−λ)f(b) for all a, b and λ between 0 and 1. Sums of convex functions are convex, which is why adding an L2 penalty to a convex loss keeps it convex.

Step 2 of 6: Local vs Global Minima

Where you start determines where you end

xf(x)basin of attraction (color = which minimum you reach)globallocalstart
LeftStart x: 2.00Right
Start x
2.00
Converged x
1.57
f(x) at min
1.19

From x=2.0, gradient descent follows the slope into a local minimum at x=1.6. The gradient is zero there, so it cannot escape. The global minimum is at x=-0.5. Move the start into a different colored basin.

Move the Start x slider, or press Show 4 starts at once. This curve has two minima, a global one near x = −0.54 and a local one near x = 1.56, and every run uses a fixed learning rate of 0.05 for 120 steps. Gradient descent only sees the slope where it stands, so the starting point alone decides the outcome. Running several random restarts and keeping the best result is the simplest defense, and it is common practice for k-means and other non-convex methods.

Step 3 of 6: Saddle Points

Flat but not a minimum

xyf > 0f < 0saddle point
x: 0.00
y: 0.00
df/dx
0.00
df/dy
0.00
|grad|
0.00

Near the saddle point the gradient is close to zero, but this is not a minimum: f(x,y) = x² − y² curves up in x and down in y. Gradient methods can stall here.

Move the x and y sliders toward the origin and watch |grad| fall. On x² − y² the Hessian has one positive and one negative eigenvalue, which is the test for a saddle. In high dimensions saddles are far more common than local minima: a critical point is a minimum only if curvature is positive in every direction, and with millions of directions some are almost always negative. Small noise from mini-batch gradients usually pushes an optimizer off a saddle.

Step 4 of 6: The Convexity Test

Second derivatives reveal curvature

xf(x)f'' = 0
f(x)f''(x)tangent
ConcaveShape: 0.50Convex
Probe x: 0.50
f(x)
2.05
f'(x)
0.88
f''(x)
-1.23
Convex?
No

f''(x) < 0 here (dashed pink below its dotted f'' = 0 line), so this region is concave. The function is not convex.

Slide Shape from Concave to Convex, then move Probe x to check the sign of f''(x) at different points. The second-derivative test needs f'' ≥ 0 at every point, not just one, which is why the Convex? readout scans the whole range. For functions of many variables the test becomes a matrix condition: the Hessian must be positive semidefinite everywhere, meaning all its eigenvalues are non-negative. Logistic regression's loss passes this test, which is why it has no spurious minima.

Step 5 of 6: Loss Landscapes

Neural networks in the wild

paramslossinputhidden (4)output
Narrow (1)Width: 4Wide (20)
Width
4
Local Minima
5
Global Min
-0.92

A moderate-width network. The bumps shrink as width increases. This curve is a schematic: its bumps are drawn to shrink as 1/width to show the trend, not computed from a real network.

Move the Width slider from Narrow (1) to Wide (20) and watch the bumps flatten against the underlying bowl. Here the bump height scales as 1/width, a toy stand-in for a real effect. The Local Minima readout drops from 5 at width 4 to 3 at width 10 and reaches 1 from width 15. Real loss surfaces have millions of dimensions, so pictures of them are low-dimensional slices. Li et al. (2018) used random two-dimensional slices to show that skip connections and greater width make the surface around good solutions noticeably smoother.

Step 6 of 6: Escaping Local Minima

Momentum and learning rate to the rescue

xf(x)start
LowMomentum: 0.50High
SmallLearning Rate: 0.080Large
Momentum
0.50
LR
0.080
Loss
3.69
Step
0

Moderate momentum accumulates velocity from past gradients, helping push through shallow local minima while staying stable.

Set Momentum and Learning Rate, then press Play or step through manually. The update here is v ← μ·v − η·∇f, then x ← x + v, starting from x = 2.5 for up to 200 steps. With momentum μ, a constant gradient builds speed up to 1/(1 − μ) times the plain step, so μ = 0.9 moves about ten times as far. Adam and SGD with momentum use this same running average of past gradients. In practice μ = 0.9 is a common default.

What is convex optimization?

Convex optimization is the problem of minimizing a convex function over a convex set. A function is convex when the straight line between any two points on its graph never dips below the graph, so it has one bowl and no false bottoms. Every local minimum of a convex problem is a global minimum, which makes these problems reliably solvable.

Many classic ML models are convex: linear and logistic regression, ridge and lasso, and support vector machines. For them, training finds the best possible parameters regardless of where it starts. Deep networks are not convex, so their loss surfaces have local minima, saddle points, and flat regions. Knowing which properties are lost explains why initialization, momentum, and learning-rate choices matter so much for them.

Key ideas

  • A convex function lies below every chord between two points on its graph.
  • In a convex problem, every local minimum is a global minimum.
  • A twice-differentiable function is convex when its second derivative, or Hessian, is non-negative everywhere.
  • Non-convex functions can have many local minima, and the start point decides which one gradient descent finds.
  • Saddle points have zero gradient but curve up in some directions and down in others.
  • Momentum averages past gradients, which helps an optimizer roll through small bumps and flat regions.

Common questions

Which machine learning models have convex loss functions?

Linear regression with squared error, logistic regression with cross-entropy, ridge and lasso regression, and linear support vector machines are all convex in their parameters. Adding a hidden layer with a nonlinear activation breaks convexity, because swapping two hidden units gives a different set of weights with the same loss.

Why do neural networks train well despite being non-convex?

Large networks seem to have many good minima with similar loss, so landing in any of them is usually fine. Most bad critical points in high dimensions are saddles rather than minima, and noisy gradients move past them. Over-parameterization also tends to connect good solutions through low-loss paths.

What is a convex set?

A set is convex if the straight segment between any two of its points stays inside it. Balls, boxes, half-spaces, and the probability simplex are convex; a ring or a crescent is not. Convex optimization requires both a convex objective and a convex feasible set.

How are convex problems solved in practice?

Smooth problems use gradient methods or Newton's method; problems with constraints often use interior-point methods. Libraries such as CVXPY let you write the problem in mathematical form and pass it to a solver. For large ML problems, first-order methods such as SGD or coordinate descent are usually preferred because each step is cheap.

Related explainers

References

  1. Boyd & Vandenberghe, "Convex Optimization", Cambridge University Press (free PDF)
  2. Dauphin et al. (2014), "Identifying and attacking the saddle point problem in high-dimensional non-convex optimization"
  3. Li et al. (2018), "Visualizing the Loss Landscape of Neural Nets"
  4. Goodfellow, Bengio & Courville, "Deep Learning", ch. 8 Optimization for Training Deep Models

Last updated