L2 Optimisation and Gradient Descent

Source: Annotated lecture PDF. Page references use PDF page numbers.

Overview

• Positive definiteness describes the sign of quadratic forms.
• Optimisation seeks good parameters; stationarity alone does not certify a minimum.
• Least squares has a closed-form solution under a rank condition; logistic regression motivates iteration.
• Gradient descent combines a direction, a step size and a stopping rule.

Positive definite and positive semidefinite matrices

For a real symmetric matrix $A$,

$$A\succ 0⟺x^{T}Ax>0\text{for every }x\ne 0,$$ $$A⪰0⟺x^{T}Ax\ge 0\text{for every }x.$$

This is a property of the quadratic form, not a requirement that every matrix entry be positive.

Key takeaway: $x^{T}Ax=x^T(Ax)$ is a dot product. For a positive definite matrix, $x$ and $Ax$ make an acute angle: this is the slide’s “same side” intuition. In Taylor’s quadratic term, the same expression describes curvature along a displacement.

Optimisation setup

Unconstrained optimisation minimises $f(w)$ over $w\in {\mathbb{R}}^n$. Constrained optimisation restricts $w$ to a feasible region, for example using $c_i(w)=0$ and $c_i(w)\ge 0$. The lecture assumes at least $f\in C^1$, sometimes $C^2$.

For model training, the decision variables are the model parameters, while the training data are fixed. An example objective is average squared prediction error:

$$f(w)=\frac{1}{m}\sum _{i=1}^m{\left[y^{(i)}-g(w\mid x^{(i)})\right]}^2.$$

Source: pp. 4–5.

Stationary points and minima

• Local minimum: $f(w^{\ast })\le f(w)$ for all $w$ in some neighbourhood of $w^{\ast }$.
• Global minimum: the inequality holds throughout the domain.
• Stationary point: $\nabla f(w^{\ast })=0$.

First-order necessary condition: an unconstrained local minimiser of a differentiable function satisfies $\nabla f(w^{\ast })=0$. This condition alone also admits maxima and stationary points that are not extrema. Do not apply it blindly to constrained boundary minima.

Key takeaway: a zero slope cannot classify a point. The diagram groups several stationary behaviours; additional structure or curvature information is needed. For a differentiable convex objective on ${\mathbb{R}}^n$, a stationary point is a global minimiser.

Worked example: least squares

With training examples as rows of $X$ and targets in $y$,

$$f(w)=\frac{1}{m}\Vert Xw-y{\Vert }_2^2,\nabla f(w)=\frac{2}{m}{X}^T(Xw-y).$$

Setting the gradient to zero gives the normal equations:

$$X^{T}Xw=X^{T}y.$$

If $X$ has full column rank, $X^{T}X$ is invertible and

$$w^{\ast }=(X^{T}X{)}^{-1}{X}^{T}y.$$

Include a column of ones in $X$ if fitting an intercept. The objective is convex because its Hessian is $2X^{T}X/m⪰0$; full column rank makes it positive definite and the minimiser unique. If the rank condition fails, the inverse formula is unavailable and minimisers need not be unique.

Source: scalar derivation, p. 10 and matrix formulation, p. 11. Remember the normal equations and rank assumption rather than every expanded scalar term.

Logistic regression: from likelihood to loss

For binary targets $y_i\in \{0,1\}$, define

$$p_i=\sigma (w^T{x}_i),\sigma (z)=\frac{1}{1+e^{-z}}.$$

The probability assigned to the observed label is $p_i^{y_i}(1-p_i{)}^{1-y_i}$. Under the lecture’s independent-observation assumption, the likelihood is the product of these terms.

Key takeaway: logarithms turn the product into a sum and preserve its maximiser because log is strictly increasing. Negating and averaging gives the negative log-likelihood / binary cross-entropy:

$$f(w)=-\frac{1}{m}\sum _{i=1}^m\left[y_i\log p_i+(1-y_i)\log (1-p_i)\right].$$

This avoids directly multiplying many tiny probabilities. Unlike least squares, the stationarity equations generally have no simple closed-form solution, so we optimise iteratively. The gradient simplifies to

$$\nabla f(w)=\frac{1}{m}\sum _{i=1}^m(p_i-y_i)x_i=\frac{1}{m}{X}^T(p-y).$$

This is an equivalent form of the gradient on p. 22: each example contributes prediction error multiplied by its features.

Gradient descent

A descent direction $d$ decreases $f(w+\alpha d)$ for every sufficiently small positive $\alpha$. For differentiable $f$, $\nabla f(w{)}^{T}d<0$ is sufficient.

From the directional derivative, the negative gradient is the Euclidean steepest descent direction. The standard update is

$$w_{k+1}=w_k-{\alpha }_k\nabla f(w_k),{\alpha }_k>0.$$

Even with fixed learning rate $\alpha$, the actual movement has length $\alpha \Vert \nabla f(w_k){\Vert }_2$. A downhill direction guarantees improvement only for sufficiently small steps: an excessive step can overshoot.

Stop using a criterion such as $\Vert \nabla f(w_k){\Vert }_2\le \epsilon$ and a hard iteration/computation limit. A small gradient signals approximate stationarity, not proof of a global minimum. Initialisation can affect the outcome for nonconvex problems.

Choosing the next iterate

Line search versus trust region, p. 26:

• Line search: choose a direction first, then choose how far to move along it.
• Trust region: set a radius, then optimise a local model within that radius to choose the step.

The lecturer’s practical emphasis on pp. 24–25 is to compare total computational cost. Fewer iterations may require more expensive information per iteration. The practical goal is a sufficiently good point within the available budget.

Important results

• $\nabla f(w^{\ast })=0$ is necessary for an unconstrained differentiable minimum, but generally insufficient.
• Least squares: $X^{T}Xw=X^{T}y$; the inverse formula requires full column rank.
• Logistic loss gradient: $X^T(p-y)/m$.
• Gradient descent: $w_{k+1}=w_k-{\alpha }_k\nabla f(w_k)$.