Recall · Lecture 5

From Derivatives to Learning

What the gradient gives us

$g_j$

one number per parameter

$\theta_j$

the parameter it belongs to

$g$

a column, shaped like $\theta$

$p$

how many parameters there are

Vote

From Derivatives to Learning

Which quantity changes?

Fitting a fixed dataset: which quantity does the update directly adjust?

1. Athe target $y^\star$
2. Bthe model weight $\theta$✓
3. Cthe observed input $x$

Ask two things of each: does $L$ depend on it, and are we free to move it?

Only $\theta$ is both. $\eta$ is in the update, but we choose it rather than learn it.

From Derivatives to Learning

A change has several contributions

$\partial L/\partial\theta_j$

how sensitive $L$ is to $\theta_j$, at the current $\theta$

$d\theta_j$

the change we make to that one parameter

the sum

the local linear model, not the exact change

From Derivatives to Learning

The sum is an inner product

$g\T$

$1\times p$, a row of rates

$d\theta$

$p\times1$, a column of increments

$g\T d\theta$

$1\times1$: the differential, exact

$o(\lVert\Delta\theta\rVert)$

what a finite step leaves over

Vote

From Derivatives to Learning

Derivative or finite change?

Which expression is an exact identity at a differentiable point?

1. A$dL=g\T d\theta$✓
2. B$\Delta L=g\T\Delta\theta$ for every step $\Delta\theta$
3. C$dL=\lVert g\rVert$

Differentials are linear. Finite changes may have a remainder.

B drops the remainder, which the picture opens up. C has no direction and no step size in it, so reversing the step would not change it.

From Derivatives to Learning

Three jobs in one learning step

(i)

one number out

(ii)

one rate per parameter out, and nothing is moved yet

(iii)

a new parameter column; this is where $\eta$ enters

Vote

From Derivatives to Learning

Where does updating happen?

In ordinary gradient descent, which operation changes a weight?

1. Athe forward pass
2. Bthe backward pass
3. C$\theta\leftarrow\theta-\eta g$✓

Look for the line that assigns a new value to $\theta$.

Forward makes values and backward makes sensitivities; both read $\theta$ and neither writes it. Only the update does, and only it has $\eta$.

Where we are

Automatic Differentiation

Remembering a computation

$v$

the forward number it holds

$u_1,\dots,u_m$

its parents, saved

$\bar v$

a second slot, filled backward

$\partial v/\partial u_i$

one local rule per parent

Automatic Differentiation

One graph, forward values

$w$

the parameter, here 2

$x,\ y^\star$

given: 3 and 4

$a,\ e$

stored forward: 6 and 2

$L$

one scalar out: 2

Vote

Automatic Differentiation

Value and sensitivity

Same graph, at node $a$. What is the pair $(a,\bar a)$?

1. A$(6,2)$✓
2. B$(2,6)$
3. C$(6,6)$

$a$ is the number the node stored going forward; $\bar a=\partial L/\partial a$ is a rate, not a value.

The node stored $2\cdot3=6$, and $\bar a=e=2$: one node, two numbers, and swapping them is B.

Automatic Differentiation

Local rules become backward callbacks

$\bar z$

the upstream factor

$\partial z/\partial u$

addition's local rule: $1$

$\bar u,\bar v$

the two parent slots

$\mathrel{+}=$

add in; a parent has other uses

callback

a function called during the backward pass

Automatic Differentiation

Multiplication uses saved values

$u,\ v$

both saved going forward

$\bar z$

the upstream factor

$v\,\bar z$

into $\bar u$: the other input

why saved

each side needs the other

Vote

Automatic Differentiation

A missing upstream factor

$z=uv$ with $u=2$, $v=3$, and $\bar z=4$ arriving. What lands in $\bar u$?

1. A$3$
2. B$8$
3. C$12$✓

$\bar u\mathrel{+}=v\,\bar z$: the local factor is the other saved input, and the chain rule multiplies it by what arrived.

$3\times4=12$. A keeps the local factor and drops $\bar z$; B uses $u$, the input the other branch needs.

Automatic Differentiation

One variable, several uses

$x$

one node, used three times

$x\cdot x$

two argument slots

$+\,x$

a third, direct use

$r$

at $x=2$ it stores 6

Automatic Differentiation

Contributions accumulate

$x$

the node, used three times

$x\cdot x$

two slots, each giving $x$

$+\,x$

the direct use, giving 1

$dr/dx$

the sum, at $x=2$: 5

Vote

Automatic Differentiation

Assignment or addition?

For $r=x\cdot x+x$ at $x=2$, what is $dr/dx$?

1. A$1$
2. B$3$
3. C$5$✓

Traversal visits $x$ once, but $x\cdot x$ has two argument slots: three contributions arrive.

All three land: $2+2+1=5$. Assignment keeps one, $2$ or $1$; $3$ is a dropped slot, not an overwrite.

Automatic Differentiation

Reverse topological order

$s:u\to v$

one input slot; vary it with the others fixed

$\bar v$

must be final already

the sum

complete when all uses report

order

any reverse topological one

Automatic Differentiation

The loss starts with one

$\bar L$

the seed: the one adjoint we set by hand

$1$

a derivative, not the value of $L$

the rest

start at 0, filled by a local rule

Automatic Differentiation

Trace the backward schedule

seed

a number put in a slot; it runs nothing

callback

what writes into the slot below it

One step, one slot. $\bar w=6$ at the end.

Vote

Automatic Differentiation

Now two runs that break a rule

Zero the slots, then seed and run. Which gives the right $\bar w$?

1. A$\bar L=L$: $L,e,a$
2. B$\bar L=1$: $L,e,a$✓
3. C$\bar L=1$: $L,a,e$

Seeding a slot is not running a node: $L$'s callback writes $\bar e$. And no node runs before every node it feeds.

C runs $a$ while $\bar a$ is $0$, so $\bar w=0$; $\bar a$ fills too late. A's seed doubles every adjoint.

Automatic Differentiation

ReLU reuses its forward state

$z$

the saved preactivation

$\mathbf 1_{z>0}$

$1$ if $z>0$, else $0$

$\bar a$

whatever arrives, any sign

at $z=0$

no derivative; $0$ by convention

Vote

Automatic Differentiation

An open gate can pass a negative gradient

$a=\max(0,z)$ with $z=2$ saved, and $\bar a=-3$ arrives. What is $\bar z$?

1. A$0$
2. B$-3$✓
3. C$3$

The mask $\mathbf 1_{z>0}$ is a lookup on the saved $z$. Nothing in the backward pass looks at the sign of $\bar a$.

$z=2>0$: the gate is open, the slope is $1$, so $\bar z=-3$. A needs a shut gate; C flips a sign nothing flips.

Automatic Differentiation

Checking a computed derivative

$\tau$

the probe step, $1/100$

$w$

restored afterwards

centred

exact here

one-sided

off by $\tau x^2/2$

Automatic Differentiation

Backward fills slots; plain SGD moves $w$

$w$

the parameter; only the optimizer assigns to it

$\bar w$

its slot; only backward and the clear write it

$\eta$

step size, here $0.1$; chosen, not computed

$\bar w=6$

read at $w=2$; it is not the gradient at $1.4$

Vote

Automatic Differentiation

Why reset gradients?

Two fresh graphs at unchanged $w$, no clearing. What is in $\bar w$?

1. Athis step's gradient only
2. Bthe old and the new, added✓
3. C$w$ updates itself

Each step builds a new graph, but the parameter and its grad slot outlive it, and the write is still $\mathrel{+}=$.

The slot reads $6$, then $12$. Across passes, clear unless you intend to accumulate.

Recall

Gradient Descent and Step Size

Choosing a parameter change

$\Delta\theta$

$p\times1$: the step, and the only thing we choose

$g$

$p\times1$: $\nabla_\theta L$ at the current $\theta$, fixed while we choose

$\approx$

the linear part only; the leftover is dropped, not zero

Gradient Descent and Step Size

Why the negative gradient?

$\eta>0$

our step size, never folded into $g$

$\sum_j g_j^2$

a sum of squares, so it is $\ge0$

$<0$

needs only $g\ne0$ and $\eta>0$

$\Delta L<0$

a different claim: the loss itself also needs a short step

Vote

Gradient Descent and Step Size

Which direction decreases the local model?

For $g\ne0$, $\eta>0$: which step makes the predicted $g\T\Delta\theta$ negative?

1. A$\Delta\theta=+\eta g$
2. B$\Delta\theta=-\eta g$✓
3. Ca nonzero step orthogonal to $g$

Read the sign of the product, not where an arrow points.

The products are $+\eta\lVert g\rVert^2$, $-\eta\lVert g\rVert^2$ and $0$. A prediction, not a certificate.

Gradient Descent and Step Size

The gradient-descent update

$\theta_t$

the current column, $p\times1$

$g_t$

read at $\theta_t$, not at $\theta_{t+1}$

$\theta_{t+1}$

the new column, same shape

$\eta_t$

one positive number per step

Gradient Descent and Step Size

A scalar quadratic exposes overshoot

$\delta_t$

$\theta_t-\theta^\star$, one number here

$\lambda>0$

the curvature of this quadratic

$1-\eta\lambda$

the multiplier: it decides every later step

Vote

Gradient Descent and Step Size

Four step-size regimes

Take $\lambda=4$. Which pair is (converges while oscillating, diverges)?

1. A$(0.4,\ 0.6)$✓
2. B$(0.1,\ 0.25)$
3. C$(0.6,\ 0.4)$

Each step multiplies the error by $1-\eta\lambda$: read its sign, then its size.

The multipliers are $-0.6$ and $-1.4$: both flip the sign, and only the second one grows.

Recall · Lecture 4

Gradient Descent and Step Size

Several curvature directions

$H$

symmetric, positive definite, $p\times p$

$Q$

orthonormal eigenvectors $q_i$

$\Lambda$

$\operatorname{diag}(\lambda_1,\dots,\lambda_p)$, each $\lambda_i>0$

$g=H\delta$

for $\delta\ne0$, parallel to $\delta$ exactly when it is an eigenvector

Gradient Descent and Step Size

Each eigenmode has one multiplier

$c_i^{(t)}$

the error's coordinate along $q_i$

$1-\eta\lambda_i$

one factor per mode; modes never mix

If some $\lambda_i=0$, that factor is $1$: the mode keeps its error for every $\eta$.

Gradient Descent and Step Size

When does every mode decay?

$\lambda_i$

the curvatures of one fixed $H\succ0$

$\lambda_{\max}$

the largest; the steep mode binds first

scope

this quadratic only, not any loss, not a network

Vote

Gradient Descent and Step Size

Which curvature limits the step?

$H=\mathrm{diag}(2,8)$. Which $\eta$ sends the error to zero from every start?

1. A$0<\eta<1$
2. B$0<\eta<\tfrac14$✓
3. C$0<\eta\le\tfrac14$

Need $|1-2\eta|<1$ and $|1-8\eta|<1$ at once.

The steep mode binds: at $\tfrac14$ the factor is $-1$ and never decays; A allows $\tfrac12$, giving $-3$. Proved for one fixed positive definite $H$; not a rule for a network.

Gradient Descent and Step Size

A complete two-parameter step

$\theta^\star=(1,-1)$

the minimiser; $H=\mathrm{diag}(2,8)$

$\theta_0=0$

so $\delta_0=(-1,1)$

$g_0$

a column: $8$ steep, $-2$ gentle

Gradient Descent and Step Size

Scaling the loss scales the update

$B$

how many terms the sum has; $B=5$ here

$g_{\mathrm{mean}}$

every entry $1/B$ as large

$\theta^\star$

unmoved: dividing by a positive $B$ keeps every comparison

every term

is scaled, not just one of them

Vote

Gradient Descent and Step Size

Which pair reproduces the step?

Which pair gives the same update $\theta-\eta g$ as the sum loss?

1. A$0.1$ with $g_{\mathrm{mean}}$
2. B$0.5$ with $g_{\mathrm{mean}}$✓
3. C$0.5$ with $g_{\mathrm{sum}}$

$g_{\mathrm{mean}}=g_{\mathrm{sum}}/5=(-0.4,1.6)$; match the amount subtracted, $\eta g=(-0.2,0.8)$.

B: $0.5(-0.4,1.6)=(-0.2,0.8)$. A shrank $g$ only; C enlarged $\eta$ only.

Convexity and Optimality

What zero gradient tells us

$e_j$

the $j$-th coordinate direction

$\tau$

a sufficiently small nonzero probe step, either sign

$g_j$

one limit, so $\ge0$ and $\le0$ at once

a corner

no limit, so no $g_j$ to set to zero

Convexity and Optimality

Stationary points have different roles

$f_1$

up along $+x_1$ and along $-x_1$: a minimum

$f_2$

down along both: a maximum

$f_3$

up along $x_1$, down along $x_2$: a saddle

$\nabla f_k(0)$

the same zero in all three, so it cannot tell them apart

Vote

Convexity and Optimality

Is a PSD Hessian at one point enough?

Definition

Convexity and Optimality

A convex domain contains segments

$C$

a set of points, the domain a convex function needs

$\alpha$

where on the segment you stand: $0$ gives $y$, $1$ gives $x$

$\alpha x+(1-\alpha)y$

every point of the segment, not only its two ends

not convex

one segment leaving $C$ is enough

Definition

Convexity and Optimality

A convex function lies below its chords

left side

the function at the interpolated point

right side

the height of the chord there

the gap

chord minus function, never negative

$C$

convex, or some segment leaves it and the left side has no value

Vote

Convexity and Optimality

Which picture satisfies the definition?

Key inequality

Convexity and Optimality

A supporting tangent gives a global bound

Certificate

Convexity and Optimality

Zero gradient now certifies a minimum

$\nabla f(x)=0$

the hypothesis, put into the tangent bound

$0\T(y-x)$

the whole linear term, gone

$f(y)\ge f(x)$

global: nothing in $C$ is lower

convex

the assumption doing the work; without it $\nabla f=0$ is necessary only, and only in the interior

Vote

Convexity and Optimality

Does convex mean a unique minimizer?

Equivalence

Convexity and Optimality

Curvature everywhere

$\nabla^2f(x)$

the Hessian at one point; $\succeq0$ means PSD there

for every $x$

the quantifier that does the work

$C^2$

twice continuously differentiable; then it is exact

one point

$-x^4$ has $\nabla^2f(0)=0$, and $-12x^2<0$ everywhere else

Convexity and Optimality

Which conclusion needs which hypothesis

left

differentiable, interior; necessary only

right

adds convexity; now sufficient and global

New objective

Convexity and Optimality

A quadratic penalty changes the problem

$L_\rho$

$L$ plus a second term

$\rho>0$

the penalty weight; chosen, not learned

$g_\rho$

the new gradient: $\nabla(\lVert\theta\rVert^2/2)=\theta$

$\theta^\star$

where $g=0$; if $\theta^\star\ne0$, $g_\rho\ne0$

A new objective, so in general a new minimiser.

Vote

Convexity and Optimality

Certifying a quadratic solution

Stochastic Gradients and Training

One dataset, many local losses

$N$

examples in the set, here $4$

$\ell_i(\theta)$

the loss on example $i$ alone

$\theta$

read by every term

$L$

one number, whatever $N$ is

Stochastic Gradients and Training

A mini-batch estimates the full gradient

$\hat g_t$

the estimate, shaped like $\theta$

$\mathcal B_t$

the indices drawn for step $t$

$B$

how many, with $B\le N$

$\theta_t$

the same in every term

Drawn uniformly without replacement from $\{1,\dots,N\}$, independently of $\theta_t$, afresh each step.

Vote

Stochastic Gradients and Training

Add gradients before updating

Stochastic Gradients and Training

Why uniform sampling has the right average

$w_i$

probability of drawing index $i$

$\nabla\ell_i$

example $i$'s own gradient

$\nabla L$

the full-data gradient

$w_i\ne\tfrac1N$

may change the average

Stochastic Gradients and Training

Unbiased at every $B$; only the spread changes

$\E[\cdot\mid\mathcal F_t]$

average over batches, given the history; a fresh uniform draw

$\sigma^2$

population variance; scalar gradients here

$\frac{N-B}{N-1}$

without replacement, $N>1$; $0$ at $B=N$

Stochastic Gradients and Training

A noisy step can raise the full loss

$c_i$

example $i$'s own lowest point

$L$

the mean of the four

$\nabla\ell_1$

one example's gradient

Stochastic Gradients and Training

First condition: no ceiling fixed in advance

$\eta_t$

step size at step $t$, chosen before training

$\sum\eta_t$

a sum of step sizes, not a distance travelled

needs

$\|\hat g_t\|\le G$ before it bounds any distance

Stochastic Gradients and Training

Second condition: the injected noise settles

$\hat g_t-g_t$

the step's error; need not shrink on its own

$\sum\eta_t^2$

how fast the steps shrink, so the error's effect does

needs

the error centred, and its second moment bounded

Vote

Stochastic Gradients and Training

Which schedule passes both series tests?

Stochastic Gradients and Training

One complete training iteration

$\theta_t$

the column before the step

$\hat g_t$

what backward produced

$\eta_t$

the schedule's size at $t$

Five operations, five different objects, and only the last one assigns to $\theta$.

Stochastic Gradients and Training

Accumulation inside one graph: required

$\bar u$

the gradient slot for $u$

$\bar v$

what arrived downstream

$\partial v/\partial s$

slot $s$ receives $u$; other slots fixed

$\mathrel{+}=$

add every use; each term carries its own $\partial v/\partial s$

Stochastic Gradients and Training

Accumulation across two backward passes: a leftover

$\hat g_i$

run $i$'s gradient, both at the same $\theta$

slot

never cleared between the two

Same arithmetic as the page before, different scope.

Stochastic Gradients and Training

Accumulation on purpose: micro-batches

$\hat g_m$

micro-batch $m$'s mean gradient

$B_m$

its size; equal sizes collapse the weights

Stochastic Gradients and Training

Accumulate once, or step per micro-batch?

left

both read at $\theta$; one step on the full-data gradient

right

$g_B$ read after the first step, so somewhere else

Vote

Stochastic Gradients and Training

Locate the training-loop bug

Stochastic Gradients and Training

A different omission: clearing, over two steps

$\hat g_s$

read at the $\theta$ the loop is standing on

slot

a running sum when line one is missing

Both loops update. Only line one differs, and they end apart.

New block

Layer Normalization

Controlling feature offset and scale

$h$

one sample’s feature column, $d\times1$

$d$

how many features, never how many samples

$z$

what the next layer reads, same shape

two per feature

a learned scale and shift, kept at the end

It controls feature offset and scale; faster training is not guaranteed.

Layer Normalization

Mean and variance over features

$h_j$

feature $j$ of this one sample

$\mu,\ v$

two scalars, built from this sample alone

$j=1,\dots,d$

the sum runs over features; no sample index appears in it

Divided by $d$, not $d-1$: the population variance of the $d$ numbers in front of us.

Layer Normalization

Step one: centre the features

$h$

one sample's features, $d\times1$

$\mu$

mean over features, not over the batch

$c$

the centred features; $\sum_i c_i=0$ always

$v$

their mean square, this sample's spread

Layer Normalization

Step two: divide by $s$, and why $\varepsilon$ is there

$s$

one positive number for this sample

$\varepsilon$

fixed, so $s$ is never $0$ on a flat sample

$u$

the normalized features; their statistics are the next vote

Layer Normalization

Step three: the learned scale and shift

$\gamma,\beta$

learned, $d\times1$ each, one pair for all samples

$\odot$

entry by entry, not a matrix product

$z$

what leaves the block, $d\times1$

Vote

Layer Normalization

What is exactly zero or one?

New $h=(0,0,3)\T$, $\varepsilon=2$. Compute $c,s,u$. Then $u$ has

1. Amean $0$, $\operatorname{mean}(u^2)=1$
2. Bmean $0$, and $\operatorname{mean}(u^2)<1$✓
3. Cno fixed mean

$\mu=1$, $c=(-1,-1,2)\T$, $v=2$, $s=2$; divide $c$ by $s$.

$u=(-1/2,-1/2,1)\T$: mean $0$, mean square $(1/4+1/4+1)/3=1/2=v/(v+\varepsilon)$.

Supplement

Layer Normalization

Where the backward pass is written down

$\nabla_z L$

from above, $d\times1$

$\nabla_h L$

back down; three routes build it

$\nabla_\gamma L,\ \nabla_\beta L$

$d\times1$ each, like the pair

• two correction terms, and a zero-sum test that passes a wrong formula
• wanted again in Lecture 10, and by a gradient check

Eleven pages, with the worked numbers and its own three votes: jingz6676.github.io/rob6013/layernorm-backward.html

Putting it together

A Complete Learning Step

The same chain rule in every block

$\bar L=1$

the only seed a reverse pass needs

$\bar v$

what arrived from downstream

$\partial v/\partial s$

slot $s$ receives $u$; other slots fixed

$\eta_t$

enters here, nowhere earlier

Worked example

A Complete Learning Step

From data to a checked parameter update

$x=(1,2),\ y^\star=(1,3),\quad w=1,\ b=0,\ \eta=0.1$

$x_i,y_i^\star$

data

$w,b$

parameters

$e_i,L$

error; mean loss

Forward → backward → update → recheck.

$g_w,g_b$

shared gradients

$L=0.25\ \to\ (w',b')=(1.1,0.05)\ \to\ L'=0.14625$

Vote

A Complete Learning Step

Choose the steps for changed data

$x=(1,3),\ y^\star=(2,2),\ w=1,\ b=0,\ \eta=0.1$. Find $L,g_w,g_b$; choose $(w',b',L')$.

$e_i$

error

$w,b$

parameters

$L$

mean loss

1. A$(0.9,0,0.5)$
2. B$(0.9,0,0.425)$✓
3. C$(0.95,0,0.45625)$

Hint: $g_w=\tfrac12\sum_i e_ix_i,\quad g_b=\tfrac12\sum_i e_i$.

$e=(-1,1),\ L=0.5,\ (g_w,g_b)=(1,0)$. Recompute the loss.

Vote

A Complete Learning Step

Diagnose before changing the optimizer

Probe $6$, rule $3$, and $\eta\cdot3\ne\eta\cdot6$ for all $\eta>0$. A right derivative still leaves step size and modelling open.

A Complete Learning Step

Three distinct claims about training

(i)

a derivation gives the rule; a probe tests the code

(ii)

a step question; $\eta$ and curvature decide it

(iii)

a data question, asked where $L$ never looked

Vote

A Complete Learning Step

Exit check and next connection

One fixed $H$, every mode. Not a network whose curvature moves, and not unseen data. Repeated steps return in Lecture 7.