Training a model is minimising a function. This lecture assembles the complete one-dimensional theory — critical points, the second-derivative test, and convexity — so that when we go to a million dimensions in Lecture 12, only the bookkeeping changes.
Let \(f:S\to\RR\) with \(S\subseteq\RR\), and \(w^\star\in S\).
Maximisers are defined by reversing the inequality. A point that is one or the other is an extremum.
The \(\delta\) in the local definition is the same \(\delta\) from Lecture 3: "in some neighbourhood". Global means everywhere; local means only that you cannot improve by looking nearby. Gradient descent, which only ever looks nearby, can only ever guarantee the local version — which is why the whole field cares so much about when the two coincide.
If \(f\) has a local extremum at an interior point \(w^\star\) of its domain, and \(f\) is differentiable at \(w^\star\), then \(f'(w^\star)=0\).
Proof (for a local minimum). By definition there is \(\delta>0\) with \(f(w^\star+h)\ge f(w^\star)\) whenever \(|h|<\delta\). So the numerator \(f(w^\star+h)-f(w^\star)\) is \(\ge0\) for all such \(h\). Now look at the difference quotient from each side:
\[ h>0:\quad \frac{f(w^\star+h)-f(w^\star)}{h} \ge 0 \quad\Longrightarrow\quad f'(w^\star)=\lim_{h\to0^+}(\cdots)\ \ge 0,\] \[ h<0:\quad \frac{f(w^\star+h)-f(w^\star)}{h} \le 0 \quad\Longrightarrow\quad f'(w^\star)=\lim_{h\to0^-}(\cdots)\ \le 0.\]The sign flips because we divide a non-negative numerator by a negative \(h\). Since \(f\) is differentiable, both one-sided limits equal the same number \(f'(w^\star)\). A number that is both \(\ge0\) and \(\le0\) is \(0\). ∎
Read the direction of that implication carefully. It says extremum ⟹ critical. It does not say the reverse. Three ways \(f'(w)=0\) fails to be a minimum:
Fermat's rule narrows the search to critical points. To sort them we use curvature, and Taylor tells us why it works. Expand about a critical point \(w^\star\), where \(f'(w^\star)=0\):
\[f(w^\star+h) = f(w^\star) + \underbrace{f'(w^\star)}_{=\,0}h + \tfrac12 f''(w^\star)h^2 + O(h^3) = f(w^\star) + \tfrac12 f''(w^\star)h^2 + O(h^3).\]
For small \(h\) the quadratic term dominates the cubic tail, and \(h^2>0\) regardless of direction. So the sign of \(f(w^\star+h)-f(w^\star)\) is the sign of \(f''(w^\star)\).
Let \(f'(w^\star)=0\) and let \(f''\) be continuous near \(w^\star\).
The third case is genuinely undecided, not a technicality: \(w^4\) (min), \(-w^4\) (max) and \(w^3\) (neither) all have \(f'=f''=0\) at the origin.
Everything so far is local. Convexity is the assumption that upgrades local statements to global ones, and it is the dividing line between optimisation problems we can solve and problems we can only attack heuristically.
\(f\) is convex on an interval \(I\) if for all \(u,v\in I\) and all \(\lambda\in[0,1]\),
\[ f\big(\lambda u + (1-\lambda)v\big) \;\le\; \lambda f(u) + (1-\lambda)f(v). \]It is strictly convex if the inequality is strict whenever \(u\neq v\) and \(\lambda\in(0,1)\).
The left side is the function evaluated somewhere on the segment between \(u\) and \(v\); the right side is the corresponding height on the straight chord joining \((u,f(u))\) to \((v,f(v))\). So convexity says: the chord never dips below the curve. Equivalently, the region above the graph is a convex set — you can stretch a rubber band between any two points on the graph and it will never cut through.
If \(f\) is twice differentiable on an interval \(I\), then
\[ f \text{ is convex on } I \quad\Longleftrightarrow\quad f''(w)\ge 0 \text{ for all } w\in I. \]And \(f''(w)>0\) everywhere implies strictly convex. (The converse of that last one fails: \(w^4\) is strictly convex but \(f''(0)=0\).)
Let \(f\) be convex on an interval \(I\). Then:
Proof of (1). Let \(w^\star\) be a local minimum, so \(f(w^\star)\le f(w)\) for all \(w\) within \(\delta\). Suppose for contradiction some \(v\in I\) has \(f(v)<f(w^\star)\). Consider points on the segment towards \(v\): for \(\lambda\in(0,1)\) close to 1, the point \(m_\lambda=\lambda w^\star+(1-\lambda)v\) lies within \(\delta\) of \(w^\star\). Convexity gives
\[ f(m_\lambda) \le \lambda f(w^\star) + (1-\lambda)f(v) < \lambda f(w^\star)+(1-\lambda)f(w^\star) = f(w^\star), \]where the strict inequality used \(f(v)<f(w^\star)\) and \(1-\lambda>0\). So \(m_\lambda\) is a nearby point with a strictly smaller value — contradicting local minimality. Hence no such \(v\) exists. ∎
This theorem is the reason the field is split in two.
One warning about vocabulary: people say "the loss surface is non-convex" to mean the loss as a function of the parameters. Cross-entropy is convex in the network's outputs; it is the composition with the network that destroys convexity. Composition does not preserve convexity, and that is the whole difficulty of deep learning in one sentence.
Let us do a complete optimisation problem from start to finish. Given data \((x_1,y_1),\dots,(x_n,y_n)\), fit the one-parameter model \(\hat y = w x\) by minimising squared error.
Least squares had a closed form. Most problems do not, and then we iterate. Lecture 6 showed the step size must satisfy \(\eta<2/L\), but \(L\) is usually unknown. The practical answer is to test each step rather than predict it.
Find and classify all critical points:
(a) \(f(w)=w^3-6w^2+9w+1\) (b) \(f(w)=we^{-w}\) (c) \(f(w)=w^4-8w^2\)
(a) \(f'=3w^2-12w+9=3(w-1)(w-3)\), so \(w=1,3\). \(f''=6w-12\).
\(f''(1)=-6<0\) → local max, \(f(1)=5\). \(f''(3)=6>0\) → local min, \(f(3)=27-54+27+1=1\).
(b) Product rule: \(f'=e^{-w}-we^{-w}=e^{-w}(1-w)\). Since \(e^{-w}>0\) always, the only
critical point is \(w=1\). Then \(f''=e^{-w}(w-2)\), so \(f''(1)=-e^{-1}<0\) → local maximum, \(f(1)=1/e\).
It is in fact the global maximum: \(f\to0\) as \(w\to+\infty\) and \(f\to-\infty\) as \(w\to-\infty\).
(c) \(f'=4w^3-16w=4w(w^2-4)=4w(w-2)(w+2)\), so \(w=0,\pm2\). \(f''=12w^2-16\).
\(f''(0)=-16<0\) → local max, \(f(0)=0\). \(f''(\pm2)=48-16=32>0\) → local minima, \(f(\pm2)=16-32=-16\).
Both minima are global (equal value, and \(f\to+\infty\) at both ends). A symmetric double well — and a
concrete example of a function with two distinct global minimisers, so the minimiser is not unique. Consistent
with the theorem: \(f\) is not convex.
Determine whether each is convex on the stated interval, using \(f''\):
(a) \(f(w)=e^{w}\) on \(\RR\) (b) \(f(w)=-\ln w\) on \((0,\infty)\) (c) \(f(w)=w\ln w\) on \((0,\infty)\) (d) \(f(w)=\log(1+e^{w})\) on \(\RR\)
Then say which machine-learning object each of (b), (c), (d) is a piece of.
(a) \(f''=e^w>0\) everywhere → strictly convex. ✓
(b) \(f'=-1/w\), \(f''=1/w^2>0\) on \((0,\infty)\) → strictly convex. ✓
ML: this is the negative log-likelihood of a single outcome, and the reason cross-entropy is convex
in the predicted probability.
(c) \(f'=\ln w+1\), \(f''=1/w>0\) on \((0,\infty)\) → strictly convex. ✓
ML: \(\sum p\ln p\) is negative entropy, so entropy \(H=-\sum p\ln p\) is concave — which is
why the uniform distribution maximises it (Lecture 2's exercise), and why maximum-entropy arguments are
well-posed.
(d) This is softplus. From Lecture 5, \(f'=\sigma(w)\), and from the same lecture
\(f''=\sigma'(w)=\sigma(1-\sigma)\). Since \(0<\sigma<1\), the product is strictly positive → strictly
convex. ✓
ML: \(\log(1+e^{-yz})\) is the logistic loss. Its convexity in \(z\) is exactly why logistic
regression is a convex problem — and why composing it with a neural network's \(z(\vt)\) is not.
Extend the least-squares derivation to the two-parameter model \(\hat y = w x + b\).
Set both partial derivatives to zero and solve the resulting \(2\times2\) system. Show that the fitted line always passes through \((\bar x,\bar y)\), the centroid of the data.
\(J(w,b)=\frac12\sum_i (wx_i+b-y_i)^2\). Treat one variable at a time (formally, these are partial derivatives — Lecture 12 makes that rigorous, but the mechanics are identical).
\[\frac{\partial J}{\partial b} = \sum_i (wx_i+b-y_i) = 0 \quad\Longrightarrow\quad w\sum x_i + nb = \sum y_i.\]Divide by \(n\): \(w\bar x + b = \bar y\). This already proves the centroid claim: setting \(x=\bar x\) in the fitted line gives \(w\bar x + b = \bar y\) ✓. It holds for any data, and it is a direct consequence of the residuals summing to zero.
\[\frac{\partial J}{\partial w} = \sum_i (wx_i+b-y_i)x_i = 0 \quad\Longrightarrow\quad w\sum x_i^2 + b\sum x_i = \sum x_iy_i.\]Substitute \(b=\bar y - w\bar x\) into the second equation:
\[w\sum x_i^2 + (\bar y-w\bar x)\,n\bar x = \sum x_iy_i \;\Longrightarrow\; w\left(\sum x_i^2 - n\bar x^2\right) = \sum x_iy_i - n\bar x\bar y.\] \[\boxed{\;\hat w = \frac{\sum_i (x_i-\bar x)(y_i-\bar y)}{\sum_i (x_i-\bar x)^2} = \frac{\Cov(x,y)}{\Var(x)}, \qquad \hat b = \bar y - \hat w\bar x.\;}\]The last rewriting uses the identities \(\sum x_iy_i - n\bar x\bar y = \sum(x_i-\bar x)(y_i-\bar y)\) and \(\sum x_i^2 - n\bar x^2 = \sum(x_i-\bar x)^2\), both worth verifying. The result is one of the most quoted formulas in statistics — slope equals covariance over variance — and you have now derived it from nothing but Fermat's rule.
Coding + proof. Consider minimising the logistic loss for a single data point with label \(y=1\):
\[ \ell(w) = \log\!\left(1+e^{-wx}\right), \qquad x>0 \text{ fixed}. \]1. Chain rule (and Lecture 5's softplus result):
\[\ell'(w) = \frac{-x e^{-wx}}{1+e^{-wx}} = -x\,\big(1-\sigma(wx)\big) = -x\,\sigma(-wx).\] \[\ell''(w) = x^2\,\sigma(wx)\big(1-\sigma(wx)\big).\]Since \(x>0\) and \(0<\sigma<1\) strictly, \(\ell''>0\) everywhere → strictly convex. ✓
2. \(\ell'(w)=-x\sigma(-wx)\) is strictly negative for every \(w\), because \(\sigma\) is never zero. So \(\ell\) is strictly decreasing on all of \(\RR\) and has no critical point. As \(w\to\infty\), \(e^{-wx}\to0\) so \(\ell(w)\to\log 1=0\); and \(\ell(w)>0\) always. Hence \(\inf\ell=0\), approached but never attained. ∎
What this means: on linearly separable data, logistic regression has no finite optimum —
the weights diverge to infinity as the model becomes ever more confident. In practice you see the training
loss creep towards zero while \(\|\vw\|\) grows without bound, the model becomes wildly overconfident, and
its probability estimates stop being calibrated. This is a real, commonly-encountered failure, not a
pathological example. It is also why sklearn.LogisticRegression applies L2 regularisation
by default — a decision that surprises people until they know this.
3. \(\ell_\lambda'' = \ell'' + \lambda > 0\), so \(\ell_\lambda\) is still strictly convex. For existence: \(\ell_\lambda(w) \ge \frac{\lambda}{2}w^2 \to \infty\) as \(|w|\to\infty\) (the function is coercive), so a minimum must be attained at a finite point. Strict convexity makes it unique. ∎
The minimiser solves \(x\,\sigma(-\hat wx) = \lambda \hat w\) — no closed form, but a well-posed problem with a guaranteed answer, which is all an iterative method needs.
import numpy as np
x, lam, eta = 1.0, 0.1, 0.5
sig = lambda z: 1/(1+np.exp(-z))
for name, grad in [("unregularised", lambda w: -x*sig(-w*x)),
("L2, lam=0.1", lambda w: -x*sig(-w*x) + lam*w)]:
w = 0.0
for _ in range(10000): w -= eta*grad(w)
print(f"{name:16s} w = {w:.6f}")The unregularised run drifts steadily upward and keeps going — after 10 000 steps it is at \(w\approx 8.52\) and still climbing logarithmically, never settling. Run it for 100 000 steps and you will get roughly \(w\approx 10.8\); there is no limit. The regularised run converges to \(w\approx 1.6335\) and stays there, with the gradient at machine zero.
Check the regularised answer against the stationarity condition: \(\sigma(-1.6335)=0.16335\) and \(\lambda\hat w = 0.1\times1.6335=0.16335\) ✓. Note also how much the regulariser pulls the weight in — from unbounded growth down to 1.63 — which is the bias-variance tradeoff appearing in its simplest possible form.
Next: Part III. Real data has more than one feature, so a parameter is a vector and a model is a matrix. Lecture 8 builds vectors, spans and inner products from the axioms, and the geometry you develop there is what makes Lecture 12's gradients intelligible rather than just notation.