Maths for AI
Topic 11 · Calculus & optimisation · ⏱ about 3 h

Optimisation: Minima, Convexity, Taylor & Lagrange

The maths of finding the best parameters.

Show:
In this topic
Beginner

Finding minima with derivatives

Training a model means finding the parameter values that make the loss as small as possible, so it is worth understanding how minimum points can be found and recognised. At the bottom of a smooth valley, the ground is flat: the slope is zero. So the first step is to look for stationary points, the places where the derivative is zero (or, with many variables, where the whole gradient is zero).

local minimumglobal minimumlocal maximumAll three have slope 0. The second derivative tells them apart.
Stationary points: the slope is zero at minima and maxima. Gradient descent started on the left would stop in the local minimum.

A zero slope alone doesn't tell you whether you are at the bottom of a valley or the top of a hill, so the second step is to look at the curvature, given by the second derivative f′′(w)f''(w). If f′′(w)>0f''(w) > 0, the slope is increasing as you move right, so the curve bends upwards like a cup and the point is a minimum. If f′′(w)<0f''(w) < 0, the curve bends downwards like a cap and the point is a maximum. With many variables there is a third possibility: the surface can curve upwards in one direction and downwards in another, like a horse's saddle. Such a point is called a saddle point, and the loss surfaces of neural networks contain enormous numbers of them.

Let's apply this to f(w)=w3−3wf(w) = w^3 - 3w. The derivative is f′(w)=3w2−3f'(w) = 3w^2 - 3, and setting it to zero gives w2=1w^2 = 1, so there are two stationary points, w=1w = 1 and w=−1w = -1. The second derivative is f′′(w)=6wf''(w) = 6w. At w=1w = 1 it equals 6, which is positive, so this is a minimum, with value f(1)=1−3=−2f(1) = 1 - 3 = -2. At w=−1w = -1 it equals −6, which is negative, so this is a maximum, with value f(−1)=−1+3=2f(-1) = -1 + 3 = 2.

There is a catch, though. As ww becomes very negative, w3w^3 becomes hugely negative, so ff keeps going down forever. The minimum we found at w=1w = 1 is only the lowest point in its neighbourhood, a local minimum. The global minimum is the lowest point anywhere, and this function doesn't have one. Gradient-based training methods only ever look at the local slope, so in general they can only promise to find a local minimum. The next section describes an important class of functions for which that limitation disappears.

Beginner

Convexity: when every local minimum is global

Some functions are shaped like a single bowl, with no bumps, ledges or secondary valleys. These are called convex functions, and they are the easiest functions to minimise. The formal definition captures the bowl shape: if you pick any two points on the graph and draw a straight line between them, the line never passes below the graph. Writing a point between aa and bb as ta+(1−t)bta + (1-t)b for some tt between 0 and 1, the condition is

convex: chord always abovenot convex: chord dips below
A function is convex if every chord lies on or above the graph. Convex functions have no misleading local minima.
f(t a+(1−t) b)≤t f(a)+(1−t) f(b). f\big(t\,a + (1-t)\,b\big) \le t\,f(a) + (1-t)\,f(b).

The left side is the height of the curve at a point between aa and bb, and the right side is the height of the straight line at the same point, so the inequality says that the curve lies on or below the chord.

In practice we rarely check this definition directly. For a function of one variable, it is enough to check that the second derivative is never negative, f′′(w)≥0f''(w)\ge0, meaning the curve always bends upwards. For a function of many variables, the equivalent test is that the Hessian matrix is positive semi-definite everywhere.

Convexity matters because of one remarkable property: for a convex function, every local minimum is also a global minimum, and any point where the gradient is zero is an optimal solution. There are no false valleys in which gradient descent could get stuck, so if training converges at all, it converges to the best answer.

It is useful to know which of the losses in this course are convex. The squared-error loss of linear regression, the log-loss of logistic regression, the ridge and lasso penalties and the hinge loss of support vector machines are all convex, which is why those models train reliably. Neural networks, k-means clustering, Gaussian mixture models and matrix factorisation are not convex, which is why their results can depend on the starting point and why techniques such as multiple restarts and careful initialisation are used.

Two simple rules let you prove convexity in most cases. First, a sum of convex functions is convex, so a total loss that adds up convex per-example losses (plus a convex penalty) is convex. Second, a convex function applied to a linear function of the weights is still convex. For example, u2u^2 is convex and u=w⊤x−yu = w^\top x - y is linear in ww, so (w⊤x−y)2(w^\top x - y)^2 is convex in ww, and adding these up over the data shows that the whole linear-regression loss is convex.

Try it

Try it: the chord test for convexity

Pick a function and move the two points. A convex function never lets the chord dip below the curve, for any pair of points.

Interactive: this part runs in your browser.

Intermediate · Maths

Taylor expansions and Lagrange multipliers

Two further tools explain much of what happens inside optimisation algorithms: the Taylor expansion, which approximates a function locally, and Lagrange multipliers, which handle constraints.

The Taylor expansion says that if you zoom in closely enough on a smooth function, it looks like a simple polynomial. Around a point ww, moving a small distance hh,

f(w+h)≈f(w)+f′(w) h+12f′′(w) h2. f(w + h) \approx f(w) + f'(w)\,h + \tfrac12 f''(w)\,h^2.

Each term adds more detail: the first is the current height, the second accounts for the slope, and the third accounts for the curvature. As a quick check, take f(x)=exf(x) = e^x at x=0x = 0, where the function and all its derivatives equal 1. The expansion gives e0.1≈1+0.1+12(0.1)2=1.105e^{0.1} \approx 1 + 0.1 + \frac12(0.1)^2 = 1.105, while the true value is 1.10517, so the approximation is excellent for a small step. With many variables, the slope becomes the gradient and the curvature becomes the Hessian: f(w+h)≈f(w)+∇f⊤h+12h⊤Hhf(w + h) \approx f(w) + \nabla f^\top h + \tfrac12 h^\top Hh.

The Taylor expansion explains why gradient descent works. Keep only the first two terms and take a step h=−η∇fh = -\eta\nabla f. The change in ff is approximately ∇f⊤h=−η∥∇f∥2\nabla f^\top h = -\eta\lVert\nabla f\rVert^2. Since a squared length is never negative, this change is negative whenever the gradient isn't zero, so a small enough step always decreases the function. The neglected curvature term is what goes wrong when the step is too large.

If we keep the curvature term as well, we can do better: instead of just stepping downhill, we can jump straight to the lowest point of the quadratic approximation. Differentiating f′(w)h+12f′′(w)h2f'(w)h + \tfrac12 f''(w)h^2 with respect to hh and setting the result to zero gives f′(w)+f′′(w)h=0f'(w) + f''(w)h = 0, so the best step is h=−f′(w)/f′′(w)h = -f'(w)/f''(w). This is Newton's method. For example, on f(w)=(w−3)2f(w) = (w - 3)^2 starting at w=0w = 0, we have f′(0)=−6f'(0) = -6 and f′′(0)=2f''(0) = 2, so the step is h=3h = 3, which lands exactly on the minimum at w=3w = 3 in a single step. Newton's method is extremely fast near a minimum, but in many dimensions it needs the inverse of the Hessian, which is too expensive for large models.

The second tool, Lagrange multipliers, handles problems where we must optimise subject to a constraint. Suppose we want to make f(x,y)f(x, y) as large as possible while staying on a curve defined by g(x,y)=0g(x, y) = 0. Picture the contour lines of ff. As we move along the constraint curve, we cross contour after contour. At the best point, the constraint curve must just touch a contour line without crossing it, because if it crossed, we could move a little further and reach a higher contour. Where two curves just touch, they share the same direction, and so their perpendiculars, the gradients, are parallel. That gives the condition

∇f=λ ∇gtogether withg(x,y)=0, \nabla f = \lambda\,\nabla g \quad\text{together with}\quad g(x, y) = 0,

where λ\lambda is an unknown number called the Lagrange multiplier.

Here is an example. Suppose we want to maximise the area f=xyf = xy of a rectangle whose sides add up to 10, so g=x+y−10=0g = x + y - 10 = 0. The gradients are ∇f=(y,x)\nabla f = (y, x) and ∇g=(1,1)\nabla g = (1, 1). The condition ∇f=λ∇g\nabla f = \lambda\nabla g gives y=λy = \lambda and x=λx = \lambda, so x=yx = y. Combined with x+y=10x + y = 10, this gives x=y=5x = y = 5 and an area of 25. The best rectangle is a square, which matches intuition.

Lagrange multipliers appear several times in this course. PCA maximises variance subject to the direction having length 1. Support vector machines maximise a margin subject to classifying the training points correctly. And the equivalence between penalised and constrained forms of regularisation is a Lagrange argument. When the constraints are inequalities (g≤0g \le 0) instead of equalities, the conditions are extended into the KKT conditions. Their most useful part is complementary slackness, λg=0\lambda g = 0: either a constraint is exactly active (g=0g = 0), or its multiplier is zero and it has no influence on the answer. This is precisely why only a few training points, the support vectors, affect an SVM's solution.

Interactive: this part runs in your browser.

Interactive. Drag the point and raise the order: the Taylor polynomial is a local copy of the function.
Code

Code: stationary points, Newton vs gradient descent, and a constrained problem

Python · NumPy + SciPy
import numpy as np
from scipy.optimize import minimize

# Stationary points of f(w) = w^3 - 3w
f, df, d2f = (lambda w: w**3 - 3*w), (lambda w: 3*w**2 - 3), (lambda w: 6*w)
for w in np.roots([3, 0, -3]):                    # solve 3w^2 - 3 = 0
    print(f"w={w:+.1f}: f''={d2f(w):+.0f} ->", "min" if d2f(w) > 0 else "max", " f =", f(w))

# Newton vs gradient descent on a poorly-scaled bowl f = 50 x^2 + 0.5 y^2
grad = lambda v: np.array([100 * v[0], v[1]])
H = np.array([[100.0, 0.0], [0.0, 1.0]])           # condition number 100
v_gd, v_nt = np.array([1.0, 1.0]), np.array([1.0, 1.0])
for k in range(50):
    v_gd = v_gd - 0.019 * grad(v_gd)               # step must be < 2/100 or it diverges
v_nt = v_nt - np.linalg.solve(H, grad(v_nt))       # one Newton step
print("GD after 50 steps:", v_gd.round(4), "  Newton after 1 step:", v_nt)

# Lagrange example: maximise xy subject to x + y = 10 (minimise -xy)
res = minimize(lambda p: -p[0] * p[1], x0=[1.0, 9.0],
               constraints=[{"type": "eq", "fun": lambda p: p[0] + p[1] - 10}])
print("constrained optimum:", res.x.round(4), " product:", round(-res.fun, 4))
Open in playground ↗
Beginner

Practice: check yourself

Work each question out (on paper, in your head, or in Python), type the answer and press ✔ Check. Fractions like 1/4 are fine. Hints and a worked answer are there when you need them.

Question 1.
Where is the minimum of f(x)=x2−6x+11f(x) = x^2 - 6x + 11? Give the xx value.
Question 2.
What is the minimum value of f(x)=x2−6x+11f(x) = x^2 - 6x + 11?
Question 3.
For f(x)=x2f(x) = x^2 and learning rate 0.1, starting at x=10x = 10, what is xx after one gradient step?
Check yourself

Quiz

1. f′(w) = 0 and f″(w) > 0 means w is a…

2. Why is convexity so useful?

3. Newton's method step in 1-D is h =

4. At a constrained optimum (Lagrange), ∇f is…

Go deeper

📚 Further reading

Trusted, mostly free sources: official documentation, well-known textbooks and courses. When you want to confirm or go deeper on anything here, start with these.

Ready