Exercises — Cost function (MSE) and gradient descent fitting

• ${\theta }_j$ — the parameter we are tuning (a number like a slope or intercept). This is what moves.
• $\alpha$ — the learning rate, a small positive number. It answers "how far do we step".
• $\frac{\partial J}{\partial {\theta }_j}$ — the partial derivative (slope of the cost surface along the ${\theta }_j$ direction). It answers "which way is downhill, and how steep".

One step = look at the slope (derivative) → decide how far to move ($\alpha$) → move in the downhill direction (the minus sign flips uphill-slope into a downhill-move).

The $\frac{1}{2}$ exists only to cancel the $2$ that the power rule drops when we differentiate $(\cdot {)}^2$. It makes the gradient tidy: $\frac{1}{n}\sum (h_{\theta }(x_i)-y_i)x_i^{(j)}$ instead of $\frac{2}{n}\sum (\dots )$.

It does not move the minimum. Scaling a whole function by a positive constant $c$ stretches its height but never shifts the horizontal location of the lowest point: if ${\theta }^{\star }$ minimises $J$, it also minimises $cJ$. So $\frac{1}{2}$ is pure convenience.

${\theta }_0$ appears alone (coefficient $1$), so $\frac{\partial h_{\theta }}{\partial {\theta }_0}=1$. ${\theta }_1$ multiplies $x_i$, so $\frac{\partial h_{\theta }}{\partial {\theta }_1}=x_i$. This is exactly why the two update rules differ: the ${\theta }_0$ update sums plain errors, the ${\theta }_1$ update sums errors weighted by $x_i$.

Predictions: $h(1)=0+1(1)=1$, $h(2)=0+1(2)=2$. Errors $e_i=h(x_i)-y_i$: $e_1=1-1=0$, $e_2=2-3=-1$. $J=\frac{1}{2\cdot 2}[0^2+(-1{)}^2]=\frac{1}{4}(1)=0.25$

First, why do the $2$s cancel here? We differentiate the inner squared term $(h_{\theta }(x_i)-y_i{)}^2$. The power rule pulls down the exponent $2$: $\frac{\partial }{\partial {\theta }_j}(h_{\theta }(x_i)-y_i{)}^2=2(h_{\theta }(x_i)-y_i)\cdot \frac{\partial h_{\theta }}{\partial {\theta }_j}$. That freshly-produced $2$ meets the $\frac{1}{2}$ sitting in front of $J$, and $2\cdot \frac{1}{2}=1$ — so the factor vanishes, leaving the clean $\frac{1}{n}\sum (h_{\theta }(x_i)-y_i)x_i^{(j)}$. That is the whole reason the $\frac{1}{2}$ was placed there.

Now plug in. Recall $x_i^{(0)}=1$ (bias feature) and $x_i^{(1)}=x_i$. Errors from 2.1: $e_1=0,e_2=-1$. Here $n=2$. $\frac{\partial J}{\partial {\theta }_0}=\frac{1}{n}\sum e_i{x}_i^{(0)}=\frac{1}{2}(0+(-1))=-0.5$ $\frac{\partial J}{\partial {\theta }_1}=\frac{1}{n}\sum e_i{x}_i^{(1)}=\frac{1}{2}(0\cdot 1+(-1)\cdot 2)=\frac{1}{2}(-2)=-1$ Both negative → both parameters should increase (subtracting a negative).

Use the old $\theta$ values for both updates (that's what "simultaneous" means). ${\theta }_0:=0-0.1(-0.5)=0.05$ ${\theta }_1:=1-0.1(-1)=1.1$ New parameters: ${\theta }_0=0.05,{\theta }_1=1.1$.

$h(1)=0.05+1.1(1)=1.15\Rightarrow e_1=1.15-1=0.15$ $h(2)=0.05+1.1(2)=2.25\Rightarrow e_2=2.25-3=-0.75$ $J=\frac{1}{4}[0.15^2+(-0.75{)}^2]=\frac{1}{4}(0.0225+0.5625)=\frac{1}{4}(0.585)=0.14625$ $0.14625<0.25$ ✓ — the cost fell, so the step went downhill.

Guide to the figure: the black rings are level curves of the cost — each ring is a set of $({\theta }_0,{\theta }_1)$ pairs with the same cost, like altitude lines on a map. The red ring is one such contour highlighted so you can see the shape clearly: it is an ellipse squashed thin along the horizontal ${\theta }_0$ axis and tall along the vertical ${\theta }_1$ axis. The black dot is the minimum. The red arrow marks the steep ${\theta }_1$ direction.

Why the shape: the ${\theta }_1$ gradient weights each error by $x_i$ (values $1,2,3$), while the ${\theta }_0$ gradient weights by $1$. Larger $x$ values inflate the ${\theta }_1$ slope, so the surface is steep along ${\theta }_1$ and shallow along ${\theta }_0$ — exactly the squashed ellipse you see.

Problem: one shared $\alpha$ must serve both directions. Set it safe for the steep ${\theta }_1$ axis → progress along the shallow ${\theta }_0$ axis is painfully slow; the path zig-zags across the valley. This is precisely what feature scaling fixes — rescaling $x$ makes the ellipse round.

Guide to the figure: the black curve is the cost bowl $J(\theta )$ over a single parameter. The red zig-zag path starts near the left wall and, because each step is too long, lands higher on the opposite wall — then higher again. Each red arrow is one gradient-descent step; watch them climb outward instead of settling into the black dot (the true minimum). That outward climb is divergence.

Why: the negative gradient points downhill, but $\alpha$ decides how far you commit to that direction. If $\alpha$ is too large you leap past the valley bottom and land higher on the opposite wall. Next step you overshoot back even further → cost diverges.

How large is "too large"? First, some vocabulary. The curvature of the bowl is how fast its slope changes as you move — a steep, tightly-curved valley has high curvature, a shallow flat one has low curvature. For a bowl in several parameters, the curvature is different along different directions; the mathematical object storing all these curvatures is the Hessian (the matrix of second derivatives of $J$). Its eigenvalues are exactly the curvatures along the surface's natural axes, and we write ${\lambda }_{\max }$ for the largest one — the steepest direction. Convergence for a quadratic needs $\alpha <\frac{2}{{\lambda }_{\max }}$: the step must be small enough not to overshoot the steepest axis. Practically: if you see $J$ increase, cut $\alpha$ by 10× and retry. Adaptive schemes live in learning-rate schedules.

$J(\theta )=\frac{1}{2n}\sum ({\theta }_0+{\theta }_1{x}_i-y_i{)}^2$ is a sum of squared linear functions of $\theta$. Each squared term is a bowl (convex); a sum of bowls is a bowl. A bowl has exactly one lowest point — no side dips to get trapped in. So every downhill path reaches the global minimum.

This "single-bowl" property is convexity; the topic is convex optimization. Note: logistic regression needs a different cost precisely because plugging its nonlinear hypothesis into MSE would break this bowl shape.

Batch: $\frac{\partial J}{\partial {\theta }_j}=\frac{1}{n}{\sum }_{i=1}^n(h_{\theta }(x_i)-y_i)x_i^{(j)}$. Drop the sum and the $\frac{1}{n}$ average, keep a single example $k$ chosen at random: ${\theta }_j:={\theta }_j-\alpha (h_{\theta }(x_k)-y_k)x_k^{(j)}$ Why this is still valid — the unbiased-estimator argument. First, one piece of notation: $\mathbb{E}[\cdot ]$ means the expected value — the long-run average of a random quantity if you repeated the random draw many times. (If you pick a random example again and again, $\mathbb{E}$ is the average of what you get.) The batch gradient is exactly the average of the $n$ per-example gradients $g_i=(h_{\theta }(x_i)-y_i)x_i^{(j)}$. If we pick $k$ uniformly at random from $\{1,\dots ,n\}$, each index is equally likely, so the expected (average) value of the single-example gradient is $\mathbb{E}[g_k]=\frac{1}{n}{\sum }_{i=1}^n{g}_i=\text{(the true batch gradient)}.$ So on average the noisy single-example step points exactly along the true downhill direction — that is what "unbiased estimator" means. Any one sample is a scattered arrow, but its average is the correct arrow, so over many steps the wander cancels and you descend. Advantage: each update costs one example instead of $n$ — huge datasets update far more often per second. Cost: the per-step noise means you usually need a shrinking $\alpha$ (schedules) to settle.

Two points determine a line exactly, so the best fit passes through both → zero error → global min. Slope ${\theta }_1=\frac{3-1}{1-0}=2$; intercept ${\theta }_0=1$ (line at $x=0$). Line: $y=1+2x$. Check errors: $h(0)=1\Rightarrow e_1=0$; $h(1)=1+2=3\Rightarrow e_2=0$. $\frac{\partial J}{\partial {\theta }_0}=\frac{1}{2}(0+0)=0,\frac{\partial J}{\partial {\theta }_1}=\frac{1}{2}(0\cdot 0+0\cdot 1)=0$ Both zero ✓ — at the minimum the surface is flat, so gradient descent would take a step of size $0$ and stop.

Build $X=\left[\begin{array}{cc}1& 0\\ 1& 1\end{array}\right]$ (first column of $1$s for the intercept), $y=\left[\begin{array}{c}1\\ 3\end{array}\right]$. Computing $(X^{\top }X{)}^{-1}{X}^{\top }y$ returns ${\theta }_0=1,{\theta }_1=2$ — the same interpolating line found by reasoning in 4.2, as it must, since an exact-fit dataset has a unique zero-residual solution. Prefer gradient descent when: $n$ (rows) or number of features is large, since the normal equation needs the $O(d^3)$ matrix inverse of $X^{\top }X$. For millions of features, iterative descent — especially SGD — is the only feasible option.

Reason 1 — sign leak (positives and negatives cancel). A cube keeps the sign of its input: $(-2{)}^3=-8$ but $(2{)}^3=+8$. So a large negative error contributes a large negative cost that can cancel a large positive error. Concretely, take two errors $e_1=+2$ and $e_2=-2$: their cubes are $+8$ and $-8$, summing to $0$. The cost reports $J=0$ — "perfect fit" — while both predictions are off by $2$. Squaring forbids this because $e^2\ge 0$ always, so errors can only add up, never cancel.

Reason 2 — no minimum to descend to (unbounded below). A valid cost must have a floor — a lowest value the algorithm can aim at. The cube has none. Fix any single example and push its prediction $h_{\theta }(x_i)\to -\infty$ (achievable by driving $\theta$ large in the right direction); then $(h_{\theta }(x_i)-y_i{)}^3\to -\infty$, so $J\to -\infty$. Gradient descent, always seeking lower cost, would ride this bottomless slope forever, sending $\theta$ off to infinity and never converging. A bowl (the square) has a finite lowest point; a cube is an endless downhill on one side.

(Bonus third reason: the cube is not convex, so it also breaks the single-global-minimum guarantee of Ex 3.3.)

Use widely different $x$ magnitudes, e.g. $(0.01,y_1)$ and $(1000,y_2)$. The ${\theta }_1$ gradient weights errors by $x_i$, so the huge $x=1000$ makes the surface enormously steep along ${\theta }_1$ and nearly flat along ${\theta }_0$ — an extreme, thin ellipse. Any single $\alpha$ safe for the steep axis ($\alpha <2/{\lambda }_{\max }$, tiny) crawls along the flat axis; any $\alpha$ big enough to move the flat axis explodes the steep one. Slow either way. The real fix is not tuning $\alpha$ but reshaping the surface: feature scaling rescales $x$ so both axes have comparable curvature, turning the ellipse round.

The recipe never changed: define a cost $J$, compute $\frac{\partial J}{\partial {\theta }_j}$ for every parameter, then step ${\theta }_j:={\theta }_j-\alpha \frac{\partial J}{\partial {\theta }_j}$. Linear regression has a simple hypothesis $h_{\theta }$, so each partial derivative is a one-line calculation (Ex 1.3). A neural network stacks many nonlinear layers, so its $h_{\theta }$ is a deep composition of functions — the output depends on the input through layer after layer. Computing $\frac{\partial J}{\partial {\theta }_j}$ for a parameter buried in an early layer therefore needs the chain rule applied repeatedly, once per layer. The single new ingredient is backpropagation: a systematic, efficient bookkeeping of that repeated chain rule, reusing each layer's stored intermediate result so all partials are computed in one backward sweep instead of recomputing from scratch. Crucially, the update rule ${\theta }_j:={\theta }_j-\alpha \frac{\partial J}{\partial {\theta }_j}$ itself is unchanged — only the way we obtain the gradient is new.

Simultaneous update means compute all gradients from ::: the old parameter values, then overwrite all at once MSE is guaranteed to have one global minimum because it is ::: convex (a sum of squared linear terms = a bowl) The $\frac{\partial h_{\theta }}{\partial {\theta }_1}$ term equals ::: $x_i$ If cost $J$ increases every iteration, the culprit is usually ::: a learning rate $\alpha$ that is too large SGD's single-example gradient is a valid step because ::: its expected value equals the true batch gradient (unbiased estimator) The single new ingredient a neural network adds to this machinery is ::: backpropagation (efficient repeated chain rule)