Machine-learning preliminaries
Preliminary note 2 of 2 · Jhony H. Giraldo · Télécom Paris, Institut Polytechnique de Paris
The companion note covered the linear algebra. This one covers the learning: how a model is specified, how it is trained, and — a section students often skip and shouldn’t — how to tell whether an experiment supports the claim made about it.
Not all of it is needed before Lecture 1. Sections on probability, the MLP, backpropagation and reading an experiment are the ones to read now. The optimization section is mostly groundwork for Lecture 4, and Jensen’s inequality is only needed for Lecture 6 — both are marked, and both can wait until the lecture that uses them.
As before, every section ends with Where this is used. The material assumes the mathematical preliminaries, particularly its sections on matrix products and matrix calculus.
1 Diagnostic: what do you actually need to read?
- You sample \(H\) of a node's \(d\) neighbours uniformly and average their features. Is the result an unbiased estimate of the true neighbour mean? What is its variance? (Probability)
- A coin has \(\Pr(\text{heads})=p\), flipped \(n\) times. Name the distribution of the number of heads and give its mean. (Probability)
- What does maximum likelihood estimation maximize, and why do we take a logarithm? (Probability)
- Why can a perceptron not represent XOR, and what fixes it? (Perceptron to MLP)
- What is the difference between a logit and a probability, and which does
CrossEntropyLossexpect? (Perceptron to MLP) - Write the derivative of the sigmoid \(\sigma(z)\) in terms of \(\sigma(z)\) itself. (Perceptron to MLP)
- In backpropagation, what exactly is being reused that makes it cheaper than computing each gradient separately? (Backpropagation)
- Mini-batch SGD gives an unbiased gradient estimate. What does that require of the sampling — and does it require the data points to be independent? (Backpropagation)
- Every local minimum of a convex function is global. Does a convex function always have a minimum, and if it does, is it unique? (Optimization)
- A paper reports 94% accuracy. Name three things you need to know before believing it beats an 89% baseline. (Reading an experiment)
- Yes, unbiased — uniform sampling makes each neighbour equally likely, so the sample mean has the true neighbour mean as its expectation. With replacement the variance is \(\sigma^{2}/H\), where \(\sigma^{2}\) is the variance across the \(d\) neighbours; without replacement it is smaller by the finite-population factor \(\frac{d-H}{d-1}\).
- Binomial\((n,p)\), with mean \(np\) and variance \(np(1-p)\).
- The probability the model assigns to the observed data, as a function of the parameters. The logarithm turns a product over data points into a sum — numerically stable, and it does not move the maximizer because \(\log\) is increasing.
- XOR is not linearly separable, and a perceptron can only draw one hyperplane. A hidden layer with a nonlinearity fixes it: two hidden units suffice.
- A logit is an unconstrained real score; a probability lies in \([0,1]\) and sums to one across classes.
CrossEntropyLossexpects logits — it applies the softmax itself, so passing it softmax output applies the softmax twice. - \(\sigma'(z)=\sigma(z)\bigl(1-\sigma(z)\bigr)\), which is at most \(1/4\) — the origin of vanishing gradients in deep sigmoid stacks.
- The gradient of the loss with respect to each layer's pre-activations. Computed once per layer and reused for every parameter in that layer, it turns a cost that would grow with the number of parameters into one forward and one backward pass.
- It requires the mini-batch to be sampled uniformly from the training set (or, equivalently, a shuffled pass). It does not require the data points themselves to be independent — the expectation is over the sampling, not over the data-generating process. This matters on graphs, where nodes are anything but independent.
- Not necessarily, and not necessarily unique. \(e^{x}\) is convex with no minimizer; \(f(x,y)=x^{2}\) is convex with a whole line of them. Strict convexity plus a minimum existing gives uniqueness.
- Three of: the split protocol and whether it leaks, the number of seeds and the variance across them, whether both numbers were tuned with the same budget, whether the difference exceeds the standard error, and whether a simple baseline (an MLP on features alone) was included.
2 Probability and estimators
2.1 The pieces you need
A random variable \(X\) takes values with probabilities. Its expectation and variance are
\[ \mathbb{E}[X]=\sum_x x\Pr(X=x), \qquad \operatorname{Var}(X)=\mathbb{E}\!\left[(X-\mathbb{E}[X])^{2}\right]=\mathbb{E}[X^{2}]-\mathbb{E}[X]^{2}. \]
Two properties carry most of the weight. Expectation is linear — \(\mathbb{E}[aX+bY]=a\mathbb{E}[X]+b\mathbb{E}[Y]\), always, whether or not \(X\) and \(Y\) are independent. Variance is not: \(\operatorname{Var}(X+Y)=\operatorname{Var}(X)+\operatorname{Var}(Y)\) requires independence (or at least zero covariance).
That asymmetry is worth remembering, because it is exactly why a sampled estimator can be unbiased while still being noisy, and why the noise is the thing you have to control.
2.2 Three distributions
Bernoulli\((p)\). One trial: \(X\in\{0,1\}\) with \(\Pr(X=1)=p\). Then \(\mathbb{E}[X]=p\) and \(\operatorname{Var}(X)=p(1-p)\). Every single edge decision in Lecture 6’s GraphRNN is a Bernoulli draw.
Binomial\((n,p)\). The number of successes in \(n\) independent Bernoulli trials:
\[ \Pr(X=k)=\binom{n}{k}p^{k}(1-p)^{n-k}, \qquad \mathbb{E}[X]=np, \qquad \operatorname{Var}(X)=np(1-p). \]
Poisson\((\mu)\). The limit of Binomial\((n,p)\) as \(n\to\infty\) with \(np=\mu\) held fixed:
\[ \Pr(X=k)=\frac{\mu^{k}e^{-\mu}}{k!}, \qquad \mathbb{E}[X]=\operatorname{Var}(X)=\mu . \]
Why this matters for graphs
In an Erdős–Rényi graph \(G_{np}\), each of a node’s \(N-1\) possible edges appears independently with probability \(p\). So its degree is Binomial\((N-1,p)\), and for large \(N\) with mean degree \(\bar{k}=p(N-1)\) fixed, approximately Poisson\((\bar{k})\).
That is the whole of Lecture 6’s negative result. A Poisson distribution has a tail that decays faster than exponentially — the probability of a node with degree \(10\bar{k}\) is astronomically small. Real networks routinely have such nodes. No choice of \(p\) fixes this, because the shape is wrong, not the parameter.
2.3 Estimators: unbiased, and how noisy
You often cannot compute a quantity exactly and must estimate it from a sample. Two questions follow: is the estimate right on average, and how far from the truth is it typically?
An estimator \(\hat{\theta}\) of \(\theta\) is unbiased if \(\mathbb{E}[\hat{\theta}]=\theta\). Its typical error is governed by \(\operatorname{Var}(\hat{\theta})\).
Worked example — sampling a node’s neighbours
A node has \(d>1\) neighbours with feature values \(x_1,\dots,x_d\), true mean \(\bar{x}\), and population variance \(\sigma^{2}=\frac{1}{d}\sum_i(x_i-\bar{x})^{2}\) — note the \(1/d\), not \(1/(d-1)\), which is the convention the correction below assumes. Computing \(\bar{x}\) costs \(O(d)\), which is too much when \(d\) is large, so sample \(H\) of them and average.
With replacement. Each draw is independent with mean \(\bar{x}\) and variance \(\sigma^{2}\), so
\[ \mathbb{E}[\hat{m}]=\bar{x}, \qquad \operatorname{Var}(\hat{m})=\frac{\sigma^{2}}{H}. \]
Unbiased, with error shrinking like \(1/\sqrt{H}\) — halving the error costs four times the samples.
Without replacement. Same mean, but a correction:
\[ \operatorname{Var}(\hat{m})=\frac{\sigma^{2}}{H}\cdot\frac{d-H}{d-1}. \]
The factor is at most \(1\), so sampling without replacement is never worse — and when \(H\ll d\) the two agree, which is the regime graph samplers work in.
The trap. The sampled mean is unbiased. But a network layer applies a nonlinearity afterwards, and in general
\[ \mathbb{E}\!\left[\sigma(\hat{m})\right]\neq\sigma\!\left(\mathbb{E}[\hat{m}]\right). \]
So the layer output can be biased even though the aggregate is not, and so can the gradient. “Can be” rather than “is”: a nonlinearity does not force bias in every case — if every sampled value lands in ReLU’s positive region, ReLU acts linearly on that sample and the equality holds. What is lost is the guarantee. Lecture 3 relies on this distinction; it is why its comparison table says “biased” rather than “unbiased”.
2.4 Maximum likelihood
Given data \(x_1,\dots,x_n\) and a model \(p_{\theta}\), the maximum likelihood estimate is the parameter under which the data is most probable. In general this means maximizing the joint likelihood,
\[ \theta^{*}=\arg\max_{\theta}\;\log p_{\theta}(x_1,\dots,x_n). \]
If the observations are independent under the model, the joint factorizes and the familiar form appears:
\[ \theta^{*}=\arg\max_{\theta}\prod_{i}p_{\theta}(x_i) =\arg\max_{\theta}\sum_{i}\log p_{\theta}(x_i). \]
When they are not independent — a sequence, for instance — use the probability chain rule, which needs no independence at all:
\[ p(x_1,\dots,x_n)=\prod_{i=1}^{n}p(x_i\mid x_1,\dots,x_{i-1}). \]
Lecture 6 uses this directly: GraphRNN factorizes a graph’s construction sequence exactly this way, each edge decision conditioned on everything generated before it.
The logarithm changes nothing about the maximizer — it is increasing — and buys two things: a sum instead of a product, so gradients decompose over data points, and numerical stability, since a product of thousands of small probabilities underflows.
Most loss functions in this course are negative log-likelihoods in disguise. Cross-entropy for a categorical model, binary cross-entropy for a Bernoulli one, and mean squared error for a Gaussian one with fixed variance.
That last one is worth seeing once, because it explains why squared error is the default for regression rather than an arbitrary choice. Model the target as \(y_i\sim\mathcal{N}(\hat{y}_i,\sigma^{2})\) with \(\sigma\) fixed. Then
\[ -\log p(y_i\mid\hat{y}_i) =\frac{(y_i-\hat{y}_i)^{2}}{2\sigma^{2}}+\log\sqrt{2\pi\sigma^{2}}, \]
and summing over \(i\) gives squared error plus a constant. Since \(\sigma\) is fixed, both the \(1/2\sigma^{2}\) factor and the additive constant are irrelevant to the minimizer. Minimizing MSE is maximum likelihood under a fixed-variance Gaussian — which also tells you when it is the wrong choice: heavy-tailed noise, or targets whose variance changes with the input.
2.5 Jensen’s inequality
Can wait until Lecture 6
Nothing before Lecture 6 needs this. Read it now if you like the material; otherwise return when GraphRNN’s training objective comes up.
For a concave function \(f\) — the logarithm, for instance —
\[ \mathbb{E}[f(X)]\leq f\!\left(\mathbb{E}[X]\right). \]
You need this in Lecture 6, so it is worth stating the setup carefully.
GraphRNN puts a distribution over sequences, not graphs. A graph’s probability is therefore the total probability of the distinct sequences that decode to it:
\[ p_{\theta}(\mathcal{G})=\sum_{s\,:\,f(s)=\mathcal{G}}p_{\theta}(s). \]
Training maximizes \(\mathbb{E}_{q}[\log p_{\theta}(s)]\) for some sampler \(q\) over valid sequences. Jensen relates the two, since for any such \(q\)
\[ \log p_{\theta}(\mathcal{G}) =\log\mathbb{E}_{q}\!\left[\frac{p_{\theta}(s)}{q(s\mid\mathcal{G})}\right] \;\geq\; \mathbb{E}_{q}\!\left[\log p_{\theta}(s)-\log q(s\mid\mathcal{G})\right], \]
so the training objective is a lower bound on the graph log-likelihood, up to the entropy of \(q\) — which is a constant when \(q\) is fixed and so does not affect the maximizer.
The point to carry: \(p_{\theta}(\mathcal{G})\) is a sum over sequences, not an average of sequence probabilities, and the training objective bounds it rather than equalling it.
Where this is used
Binomial and Poisson degrees are Lecture 6’s Erdős–Rényi section. Unbiasedness and sampling variance are Lecture 3’s neighbour sampling and Exercise 3. Maximum likelihood and the chain rule are Lecture 1’s random-walk objective and Lecture 6’s deep-generative-models section. Jensen is Lecture 6’s Exercise 5.
3 From a linear model to an MLP
3.1 The linear model
A linear model scores an input \(\mathbf{x}\in\mathbb{R}^{F}\) by
\[ z=\mathbf{w}^{\top}\mathbf{x}+b . \]
Geometrically, \(\{\mathbf{x}:\mathbf{w}^{\top}\mathbf{x}+b=0\}\) is a hyperplane, \(\mathbf{w}\) is its normal, and the sign of \(z\) says which side you are on. The perceptron classifies by that sign.
Stacking \(H\) such units gives a layer, written for a whole batch of \(N\) inputs as
\[ \mathbf{Z}=\mathbf{X}\mathbf{W}+\mathbf{1}\mathbf{b}^{\top}, \qquad \mathbf{X}\in\mathbb{R}^{N\times F},\ \ \mathbf{W}\in\mathbb{R}^{F\times H},\ \ \mathbf{b}\in\mathbb{R}^{H},\ \ \mathbf{Z}\in\mathbb{R}^{N\times H}, \]
where \(\mathbf{1}\in\mathbb{R}^{N}\) is a column of ones, so \(\mathbf{1}\mathbf{b}^{\top}\) copies the same bias row onto every one of the \(N\) inputs.
Note the convention, because it persists through the whole course: features are rows, and the weight matrix multiplies from the right.
3.2 Why one layer is not enough
A single linear layer can only produce linearly separable decision regions. The standard demonstration is XOR: four points, \((0,0)\) and \((1,1)\) in one class, \((0,1)\) and \((1,0)\) in the other. No line separates them, so no perceptron represents XOR.
Composing linear maps does not help — \(\mathbf{X}\mathbf{W}_1\mathbf{W}_2=\mathbf{X}(\mathbf{W}_1\mathbf{W}_2)\) is again a single linear map. The nonlinearity is what makes depth mean anything, and this exact collapse is what Lecture 3 exploits deliberately to derive SGC and Lecture 5 to derive LightGCN.
3.3 The multilayer perceptron
Interleave linear maps with a pointwise nonlinearity \(\sigma\):
\[ \mathbf{H}^{(0)}=\mathbf{X}, \qquad \mathbf{H}^{(\ell+1)}=\sigma\!\left(\mathbf{H}^{(\ell)}\mathbf{W}^{(\ell)}+\mathbf{1}\mathbf{b}^{(\ell)\top}\right). \]
Compare this with the GCN layer you will meet in Lecture 2, written with the same bias convention:
\[ \mathbf{H}^{(\ell+1)}=\sigma\!\left(\hat{\mathbf{A}}_{\mathrm{sl}}\,\mathbf{H}^{(\ell)}\mathbf{W}^{(\ell)}+\mathbf{1}\mathbf{b}^{(\ell)\top}\right), \qquad \hat{\mathbf{A}}_{\mathrm{sl}}=\tilde{\mathbf{D}}^{-1/2}(\mathbf{A}+\mathbf{I})\tilde{\mathbf{D}}^{-1/2}, \]
where \(\tilde{\mathbf{D}}\) is the degree matrix of \(\mathbf{A}+\mathbf{I}\). (The bias is a single row vector broadcast down the \(N\) rows, which is what \(\mathbf{1}\mathbf{b}^{\top}\) means; PyTorch Geometric layers include one by default.)
The only difference is \(\hat{\mathbf{A}}_{\mathrm{sl}}\). It is an MLP with one extra matrix that mixes rows — that is, that lets nodes see their neighbours. Set \(\hat{\mathbf{A}}_{\mathrm{sl}}=\mathbf{I}\) and the two coincide exactly.
Two qualifications. The self-loops matter: \(\hat{\mathbf{A}}\) without them is a different operator, and Lecture 2 spends a page on why the loops were added. And this comparison describes this layer, not every GNN — GAT’s coefficients are learned, and message-passing networks in general need not be a matrix product at all.
3.4 Activations
\[ \operatorname{ReLU}(z)=\max(0,z), \qquad \sigma(z)=\frac{1}{1+e^{-z}}, \qquad \operatorname{LeakyReLU}(z)=\max(\alpha z,z). \]
ReLU is the default in hidden layers. The sigmoid squashes to \((0,1)\) and is read as a probability. LeakyReLU keeps a small slope for negative inputs and appears in Lecture 2’s attention mechanism.
Their derivatives are worth memorizing, because they are what backpropagation multiplies by:
\[ \operatorname{ReLU}'(z)=\mathbb{1}[z>0], \qquad \sigma'(z)=\sigma(z)\left(1-\sigma(z)\right). \]
The sigmoid derivative is at most \(1/4\) and is nearly zero when \(|z|\) is large — the saturation that makes deep sigmoid networks hard to train, and part of why ReLU took over.
3.5 Softmax, logits, and probabilities
For a vector of scores \(\mathbf{z}\in\mathbb{R}^{C}\), the softmax produces a distribution over \(C\) classes:
\[ \operatorname{softmax}(\mathbf{z})_c=\frac{e^{z_c}}{\sum_{c'}e^{z_{c'}}} . \]
The raw scores \(\mathbf{z}\) are called logits. They are unbounded and need not sum to anything; the softmax converts them into probabilities.
The single most common bug in this material
torch.nn.CrossEntropyLoss applies log_softmax internally. It expects logits.
If your model already ends with a softmax and you pass its output to CrossEntropyLoss, the softmax is applied twice. The model still trains — but the effective probabilities are flattened toward uniform, gradients shrink, and convergence is much slower. There is no error message.
Pick a convention and hold it:
- return logits, use
CrossEntropyLoss; or - return
log_softmax, useNLLLoss.
The binary case has the same trap and the same fix: BCEWithLogitsLoss takes logits and applies the sigmoid internally, while BCELoss takes probabilities and expects you to have applied it already. Prefer the logits version — it is the numerically stable one.
Lecture 2’s Check 6 flags this again in the PyTorch Geometric code, because it is that easy to do.
3.6 Loss functions
For regression, mean squared error:
\[ \mathcal{L}_{\text{MSE}}=\frac{1}{n}\sum_{i}(y_i-\hat{y}_i)^{2}. \]
For binary classification with \(\hat{p}=\sigma(z)\), binary cross-entropy:
\[ \mathcal{L}_{\text{BCE}}=-\left[y\log\hat{p}+(1-y)\log(1-\hat{p})\right]. \]
For \(C\) classes with one-hot \(\mathbf{y}\) and \(\hat{\mathbf{p}}=\operatorname{softmax}(\mathbf{z})\), cross-entropy:
\[ \mathcal{L}_{\text{CE}}=-\sum_{c}y_c\log\hat{p}_c . \]
Worked example — the gradient that makes everything simple
Take binary cross-entropy composed with the sigmoid, and differentiate with respect to the logit \(z\). Using \(\hat{p}=\sigma(z)\) and \(\sigma'=\sigma(1-\sigma)\):
\[ \frac{\partial\mathcal{L}_{\text{BCE}}}{\partial z} =-\left[\frac{y}{\hat{p}}-\frac{1-y}{1-\hat{p}}\right]\hat{p}(1-\hat{p}) =-\left[y(1-\hat{p})-(1-y)\hat{p}\right] =\hat{p}-y . \]
The gradient is just the prediction minus the target. Every factor cancels. The same happens for softmax with cross-entropy, giving \(\hat{\mathbf{p}}-\mathbf{y}\).
Mind the reduction. This is the gradient for one example. If the loss is averaged over \(n\) examples, every gradient below carries an extra \(1/n\), and if it is summed, it does not. A mismatch here rescales the effective learning rate rather than producing an error message, so fix the convention once and keep it.
This is not a coincidence: it is what makes these particular loss–activation pairs the standard ones. It is also a second reason to keep the softmax inside the loss — the combined form is numerically stable, whereas computing \(\log\) of an explicit softmax is not.
Where this is used
The MLP-versus-GCN comparison is Lecture 2’s section on building a GNN from filters. ReLU, LeakyReLU and softmax appear throughout Lectures 1, 2 and 5. Logits versus probabilities is Lecture 2’s Check 6. Cross-entropy is Lecture 2’s node-classification loss; BCE is Lecture 5’s binary loss and Lecture 6’s edge loss; MSE is Lecture 4’s reconstruction and forecasting loss.
4 Backpropagation and stochastic gradient descent
4.1 Gradient descent
To minimize \(\mathcal{L}(\boldsymbol{\theta})\), step downhill:
\[ \boldsymbol{\theta}\leftarrow\boldsymbol{\theta}-\eta\,\nabla_{\boldsymbol{\theta}}\mathcal{L}, \]
with \(\eta\) the learning rate. Too small and progress is slow; too large and the iterates overshoot and can diverge. The optimization section makes the safe range precise.
4.2 Backpropagation is the chain rule, organized
For a two-layer network with \(\mathbf{Z}^{(1)}=\mathbf{X}\mathbf{W}^{(0)}\), \(\mathbf{H}=\sigma(\mathbf{Z}^{(1)})\), \(\mathbf{Z}^{(2)}=\mathbf{H}\mathbf{W}^{(1)}\) and a loss \(\mathcal{L}\), define the error signal at each layer as the gradient of the loss with respect to that layer’s pre-activation:
\[ \boldsymbol{\delta}^{(2)}=\frac{\partial\mathcal{L}}{\partial\mathbf{Z}^{(2)}}, \qquad \boldsymbol{\delta}^{(1)}=\frac{\partial\mathcal{L}}{\partial\mathbf{Z}^{(1)}}. \]
Then the whole algorithm is three lines:
\[ \boldsymbol{\delta}^{(2)}=\hat{\mathbf{P}}-\mathbf{Y} \qquad\text{(from the worked example above)}, \] \[ \boldsymbol{\delta}^{(1)}=\left(\boldsymbol{\delta}^{(2)}\mathbf{W}^{(1)\top}\right)\circ\sigma'\!\left(\mathbf{Z}^{(1)}\right), \] \[ \frac{\partial\mathcal{L}}{\partial\mathbf{W}^{(1)}}=\mathbf{H}^{\top}\boldsymbol{\delta}^{(2)}, \qquad \frac{\partial\mathcal{L}}{\partial\mathbf{W}^{(0)}}=\mathbf{X}^{\top}\boldsymbol{\delta}^{(1)}. \]
Read the middle line: to push the error back through a layer, multiply by the transpose of its weight matrix and then multiply elementwise by the derivative of its activation. Read the last line: the gradient for a weight matrix is its input transposed times the error signal coming back.
What backpropagation actually saves
A network with \(L\) layers has parameters in all of them, and the loss depends on every one through a long chain. Computing each parameter’s gradient independently would re-walk that chain each time — cost quadratic in depth.
Backpropagation computes \(\boldsymbol{\delta}^{(\ell)}\) once per layer and reuses it for every parameter in that layer, walking the chain a single time. The cost of the backward pass is then about twice the forward pass, regardless of the number of parameters.
That is the whole idea: it is not a different derivative rule, it is the chain rule with intermediate results cached. Which is also why the forward activations must be kept in memory until the backward pass uses them — and why activation memory, not parameter memory, is what limits full-batch training in Lecture 3.
4.3 Stochastic gradient descent
Training losses are averages over data points:
\[ \mathcal{L}(\boldsymbol{\theta})=\frac{1}{n}\sum_{i=1}^{n}\mathcal{L}_i(\boldsymbol{\theta}). \]
Computing \(\nabla\mathcal{L}\) exactly costs a pass over all \(n\) points. Instead sample a mini-batch \(\mathcal{B}\) of size \(m\) and use
\[ \hat{\mathbf{g}}=\frac{1}{m}\sum_{i\in\mathcal{B}}\nabla\mathcal{L}_i . \]
Why this is legitimate — and what it does not require
If the indices in \(\mathcal{B}\) are drawn uniformly from \(\{1,\dots,n\}\), then by linearity of expectation
\[ \mathbb{E}[\hat{\mathbf{g}}]=\frac{1}{n}\sum_{i=1}^{n}\nabla\mathcal{L}_i=\nabla\mathcal{L}. \]
The estimate is unbiased. Notice what that argument used: uniform sampling of the indices, and nothing else.
It did not require the data points to be statistically independent, or identically distributed, or anything else about where the data came from. The sum is a fixed finite set of numbers, and we are sampling terms from it uniformly.
This matters because on a graph the data points are emphatically not independent — neighbouring nodes share features and structure. That does not invalidate mini-batch SGD. What does break on graphs is something else entirely: computing \(\mathcal{L}_i\) for a node requires its neighbours’ activations, so the terms are not independently computable. Lecture 3 is about that problem, and Lecture 3’s Check on SGC turns on exactly this distinction.
Larger batches give lower-variance gradients at higher cost per step. Adam adapts a per-parameter learning rate from running estimates of the gradient’s first and second moments; it is the default optimizer throughout the course, and for present purposes you can treat it as SGD that needs less tuning.
Where this is used
The MLP backward pass is the template for training every model in the course. Activation memory is Lecture 3’s memory-wall argument. The unbiasedness argument and its scope are Lecture 3’s SGC discussion. Adam appears in Lectures 2, 4 and 5.
5 Optimization, as far as the course needs it
Mostly groundwork for Lecture 4
Gradient descent and the learning rate are used from Lecture 2 onward. Everything about convexity, condition numbers and the Hessian is there for Lecture 4’s reconstruction problem, and can be read then.
The course uses a narrow slice of convex optimization: convex quadratics, when their minimizer is unique, and how fast gradient descent gets there. There is no duality or KKT theory here because no lecture uses them.
5.1 Convexity
A function \(f\) is convex if for all \(\mathbf{x},\mathbf{y}\) and \(t\in[0,1]\),
\[ f\!\left(t\mathbf{x}+(1-t)\mathbf{y}\right)\leq t f(\mathbf{x})+(1-t)f(\mathbf{y}) \]
— the chord lies above the function. For twice-differentiable \(f\), this is equivalent to the Hessian \(\nabla^{2}f\) being PSD everywhere.
The property that matters: for a convex function, every local minimum is a global minimum. No local traps.
Note what that does not say. It does not promise a minimum exists: \(f(x)=e^{x}\) is convex on \(\mathbb{R}\), with infimum \(0\) that is never attained. And it does not promise uniqueness. Existence and uniqueness are separate conditions, and the next two subsections give each of them.
5.2 Convex does not mean unique
This is the point students most often get wrong, and Lecture 4 depends on it.
Take the quadratic \(f(\mathbf{x})=\tfrac12\mathbf{x}^{\top}\mathbf{A}\mathbf{x}-\mathbf{b}^{\top}\mathbf{x}\) with \(\mathbf{A}\) symmetric PSD. Then \(\nabla f=\mathbf{A}\mathbf{x}-\mathbf{b}\) and \(\nabla^{2}f=\mathbf{A}\), so \(f\) is convex and any stationary point is a global minimum.
Now suppose \(\mathbf{A}\) is only semi-definite, so it has a null space: some \(\mathbf{v}\neq\mathbf{0}\) with \(\mathbf{A}\mathbf{v}=\mathbf{0}\). Two things can happen, and which one depends on \(\mathbf{b}\).
A minimizer exists only if \(\mathbf{b}\in\operatorname{range}(\mathbf{A})\). Otherwise \(\mathbf{b}\) has a component along the null space, and moving along that direction decreases \(f\) without bound: \(f(t\mathbf{v})=-t\,\mathbf{b}^{\top}\mathbf{v}\to-\infty\). Convex, and unbounded below.
When it does exist, it is not unique. For any minimizer \(\mathbf{x}^{*}\), the whole line \(\mathbf{x}^{*}+t\mathbf{v}\) has the same gradient and the same value. A flat direction, an infinite set of minimizers, and convexity throughout.
Uniqueness needs \(\mathbf{A}\) positive definite — all eigenvalues strictly positive, no flat directions. That also gives existence, since \(\operatorname{range}(\mathbf{A})\) is then everything.
Why this is not a technicality
The graph Laplacian is PSD but never positive definite: \(\mathbf{L}\mathbf{1}=\mathbf{0}\) always. So the regularizer \(\mathbf{x}^{\top}\mathbf{L}\mathbf{x}\) is flat along constants — adding the same number to every node leaves it unchanged.
Whether the objective inherits that flatness depends on the other term. A data term like \(\Vert\mathbf{x}-\mathbf{y}\Vert^{2}\) is strictly convex and removes the flat direction entirely. The problem arises only when the data term is also blind to it.
Lecture 4 has a sharper version. If a sensor is unobserved at every time step, then shifting that sensor’s whole series by a constant changes neither the data term (nothing is observed there) nor the temporal-difference penalty (a constant has zero difference). That sensor’s level is unrecoverable, and no amount of convexity helps. Recovering it requires a sampling condition on the data, not a better solver.
5.3 Condition number and convergence
For gradient descent on a quadratic with Hessian \(\mathbf{A}\), the useful quantity is the condition number
\[ \kappa(\mathbf{A})=\frac{\lambda_{\max}(\mathbf{A})}{\lambda_{\min}(\mathbf{A})}. \]
For a positive definite quadratic with the optimal constant step \(\eta=\dfrac{2}{\lambda_{\max}+\lambda_{\min}}\), the Euclidean error contracts by a factor of at most \(\dfrac{\kappa-1}{\kappa+1}\) per iteration. (This is a worst-case bound for that specific setting; it is not a general guarantee for arbitrary convex functions.) So:
- \(\kappa\approx1\) — level sets nearly spherical, gradient descent goes almost straight to the minimum;
- \(\kappa\) large — level sets are elongated valleys, and the iterates zig-zag across them, making slow progress along the floor;
- \(\kappa=\infty\) — a flat direction, and the minimizer is not unique at all.
For a graph Laplacian \(\lambda_{\min}=0\), so \(\kappa(\mathbf{L})=\infty\). Lecture 4’s Sobolev smoothness replaces \(\mathbf{L}\) by \((\mathbf{L}+\epsilon\mathbf{I})^{\beta}\) precisely to move that smallest eigenvalue off zero.
5.4 Choosing a step size
If \(\nabla f\) is Lipschitz with constant \(L\) — meaning \(\|\nabla f(\mathbf{x})-\nabla f(\mathbf{y})\|\leq L\|\mathbf{x}-\mathbf{y}\|\), and for a quadratic \(L=\lambda_{\max}(\mathbf{A})\) — then gradient descent converges for any
\[ 0<\eta<\frac{2}{L}, \]
which is why \(\eta=1/L\) is a safe default. This is where the step sizes in Lecture 4’s reconstruction code come from.
Two caveats. The bound is open at both ends: at \(\eta=2/L\) exactly, the component along \(\lambda_{\max}\) is multiplied by \(|1-2|=1\) every step and neither grows nor decays. And Lipschitz continuity gives convergence of the iterates for a convex \(f\); it does not by itself guarantee that a global minimizer exists to converge to.
5.5 Closed form versus iteration
Setting \(\nabla f=\mathbf{0}\) for a quadratic gives the linear system \(\mathbf{A}\mathbf{x}=\mathbf{b}\), so a closed-form solution exists whenever \(\mathbf{A}\) is invertible. It is often impractical anyway: a generic dense direct solve costs \(O(n^{3})\), and forming \(\mathbf{A}\) at all may be impossible. Sparse direct methods and structured solvers can do far better than \(O(n^{3})\) when the structure permits — the honest argument for iterating is not that direct solving is always cubic, but that it needs the matrix assembled, whereas an iterative method needs only the ability to apply it.
Lecture 4 is the case in point. Its reconstruction problem has a closed form, but the operator acts on \(MN\) unknowns — for 1000 sensors over 500 time steps, a \(500\,000\times500\,000\) system that is never formed explicitly. The objective is instead evaluated through sparse products with \(\mathbf{L}\) and \(\mathbf{D}_h\), which is exactly the matrix-free setting iterative methods are built for.
Where this is used
Convexity and the Hessian are Lecture 4’s reconstruction section. Convex-but-not-unique is Lecture 4’s Check 5. Condition number and Sobolev smoothness are Lecture 4’s Sobolev discussion. The Lipschitz step size is in Lecture 4’s figure-generation code. Closed form versus iteration is Lecture 4’s TGSR discussion.
6 Reading an experiment
This section is not mathematics, and it is the one most likely to change how you read the rest of the course. Every lecture presents figures that claim a method works. Knowing what such a figure can and cannot establish is part of the subject.
6.1 Splits, and what leaks
Data is divided three ways:
- training — the model fits these;
- validation — hyperparameters are chosen on these;
- test — reported once, at the end.
Leakage is any path by which information reaches the model that would not be available at prediction time under the protocol you have declared. That last clause matters, and on graphs it is where most confusion lives — so declare the protocol first.
Three protocols, three different rules
Transductive node classification. The whole graph and all node features are available during training; only the test labels are withheld. Seeing test nodes’ features and their edges is not leakage — it is the setting, and it is what the original GCN paper evaluates (Kipf and Welling 2017). Using test labels, directly or through a label-derived feature, is.
Inductive. The model must handle nodes or graphs unseen at training time. Test nodes and their edges are removed from the training graph, so nothing about them may influence training.
Link prediction. The held-out edges are the targets, so they must be removed from the message-passing graph and from anything derived from it before training. This is the one that catches people: fit the graph with all edges present, hide 10% for testing, and the model has already seen the answers through the structure. Degrees, centralities and embeddings all have to be recomputed on the training graph.
Two forms of genuine leakage are worth naming.
Choosing hyperparameters on the test set. If you try ten settings and report the best test score, that score is a maximum over ten draws, not an estimate of performance. Lecture 4’s reconstruction figure is explicitly labelled an oracle-tuned illustration for exactly this reason: its regularization weight was chosen against the complete ground truth, which no real deployment can do.
Ignoring time. In a temporal setting, any feature computed from data after the prediction point leaks, however innocuous it looks.
6.2 Baselines
A number means nothing alone. “94% accuracy” is only interpretable against what a simpler method achieves. Useful baselines in this course:
| setting | baseline that must be beaten |
|---|---|
| node classification | an MLP on features with no graph at all |
| link prediction / recommendation | most-popular; plain matrix factorization |
| forecasting | persistence — predict the last observed value |
| graph generation | a fitted classical model such as \(G_{np}\) |
The features-only MLP deserves emphasis. If a GNN does not beat it, then under that experiment the graph has not been shown to help — which is not the same as proving the graph carries no useful information. A different architecture, a different graph construction, or a different split might extract it. But the burden has shifted: the claim that the graph matters now needs evidence.
6.3 Seeds and variance
Neural network training is stochastic: initialization, batch order, dropout, and the data split all involve randomness. A single run is a sample, not a measurement.
Report a mean and a spread over several seeds — and then reason about the uncertainty of the difference, not about the spread alone.
A 1.5-point gap with a per-run standard deviation of 2 points is not automatically meaningless: precision improves with the number of runs. With \(n\) independent runs of each method, the standard error of the difference is \(\sqrt{s_1^{2}/n+s_2^{2}/n}\), which for \(s=2\) and \(n=100\) is about \(0.28\) points — a 1.5-point gap would then be well supported. With \(n=3\) it is about \(1.6\) points, and the same gap tells you almost nothing.
Two refinements worth knowing. If both methods are run on the same splits and seeds, compare paired differences: the shared variation cancels and the comparison is far more precise. And distinguish the two sources of randomness — variation across seeds on one dataset is a different question from variation across datasets, and a method that wins on one benchmark has not been shown to win in general.
When a figure in these notes rests on a single seed, its caption says so.
6.4 Reading a plot
- What is on the axes, and is either logarithmic? A straight line means a power law on log–log, and exponential behaviour on semi-log.
- Is this a measurement, a bound, or a schematic? They look identical when plotted together. Lecture 3’s computational-graph figure deliberately puts a measured curve and three upper bounds on one axis and warns about it; Lecture 6’s cost figure marks its reference slope as not a measurement.
- Is the comparison like for like? Same data, same tuning budget, same evaluation. Lecture 6’s degree-distribution panel puts a 77-node real graph beside 5000-node models, and says so, because the comparison is an anchor and not a matched control.
- What is missing? No error bars, no baseline, no statement of how hyperparameters were chosen, or a comparison where only one method was tuned.
Where this is used
Everywhere. Every computed figure in Lectures 2 to 6 states its generator, seed count and tuning method, and several state explicitly what they do not show. Lecture 3’s Exercise 7, Lecture 4’s Exercise 6 and Lecture 5’s Exercise 8 are all investigations built on this section — they ask you to test a claim rather than confirm one.
7 Exercises
7.1 Exercise 1 — Sampling variance
A node has \(d=100\) neighbours with feature variance \(\sigma^{2}=4\). Compute the standard deviation of the sampled mean for \(H\in\{5,10,25\}\), with and without replacement. At which \(H\) does the finite-population correction change the answer by more than 10%?
7.2 Exercise 2 — Poisson degrees
Fit \(G_{np}\) to a named network rather than a remembered statistic. Take a snapshot you can download — the SNAP ego-Facebook graph (\(N=4039\), \(|\mathcal{E}|=88\,234\), mean degree \(\bar{k}\approx43.7\)) is a convenient one — and set \(p=\bar{k}/(N-1)\) so the model matches its mean degree.
Now compare the same event on both sides: the fraction of nodes with degree \(\geq 100\). Measure it in the data, then compute it under the Poisson approximation with the same \(\bar{k}\). By how many orders of magnitude do they differ?
To see how light the Poisson tail is on its own, evaluate \(\Pr(D\geq100)\) for mean \(10\): it is about \(5.4\times10^{-63}\), of which \(\Pr(D=100)\approx4.86\times10^{-63}\) — the tail is dominated by its first term, which is itself the signature of a distribution that decays faster than exponentially.
7.3 Exercise 3 — XOR
Show that no \((\mathbf{w},b)\) classifies XOR correctly. Then construct a two-layer network with two hidden ReLU units that does, and verify it on all four inputs.
7.4 Exercise 4 — The cancelling gradient
Derive \(\partial\mathcal{L}_{\text{CE}}/\partial\mathbf{z}=\hat{\mathbf{p}}-\mathbf{y}\) for softmax with cross-entropy. Then explain what goes wrong numerically if you compute \(\operatorname{softmax}\) and \(\log\) as separate steps for a logit of \(z=800\).
7.5 Exercise 5 — Backpropagation by hand
Take \(\mathbf{X}=\begin{bmatrix}1&2\\ -1&3\end{bmatrix}\), \(\mathbf{W}^{(0)}=\begin{bmatrix}1&-1\\ 0&2\end{bmatrix}\), ReLU, \(\mathbf{W}^{(1)}=[1,\,-2]^{\top}\), a linear output \(\mathbf{Z}^{(2)}=\mathbf{H}\mathbf{W}^{(1)}\), targets \(\mathbf{Y}=[1,\,0]^{\top}\), and the mean-reduced loss \(\mathcal{L}=\tfrac{1}{n}\Vert\mathbf{Z}^{(2)}-\mathbf{Y}\Vert_F^{2}\) with \(n=2\).
Note that the output error is not \(\hat{\mathbf{P}}-\mathbf{Y}\) here: that form belongs to sigmoid-with-BCE or softmax-with-cross-entropy. For this loss and a linear output,
\[ \boldsymbol{\delta}^{(2)}=\frac{2}{n}\left(\mathbf{Z}^{(2)}-\mathbf{Y}\right). \]
The other two backpropagation equations apply unchanged. Run the forward pass by hand, compute both weight gradients, and verify one entry with a central finite difference \((\mathcal{L}(w+h)-\mathcal{L}(w-h))/2h\) at \(h=10^{-5}\).
Check first that no hidden pre-activation is zero. ReLU is not differentiable there, and taking the derivative to be \(0\) is an implementation convention rather than a fact — a finite difference across that point will disagree with the analytic gradient.
7.6 Exercise 6 — Convex but not unique
Let \(\mathbf{A}=\begin{bmatrix}1&1\\1&1\end{bmatrix}\) and \(\mathbf{b}=[1,1]^{\top}\). Show \(f(\mathbf{x})=\tfrac12\mathbf{x}^{\top}\mathbf{A}\mathbf{x}-\mathbf{b}^{\top}\mathbf{x}\) is convex, find all its minimizers, and identify the flat direction. What is \(\kappa(\mathbf{A})\)?
7.7 Exercise 7 — Step size
For \(f(\mathbf{x})=\tfrac12\mathbf{x}^{\top}\mathbf{A}\mathbf{x}\) with \(\mathbf{A}=\operatorname{diag}(1,100)\), determine the interval of constant step sizes for which gradient descent converges from \([1,1]^{\top}\), and identify its upper endpoint. Note that the endpoint itself is excluded: state what the second coordinate does at \(\eta=2/L\) exactly, and why it neither converges nor diverges there.
Then run from \([1,1]^{\top}\) with \(\eta=1/L\), \(\eta=0.1/L\), and \(\eta\) just above and just below \(2/L\), and plot the error. Relate the contraction rate you observe to \(\kappa(\mathbf{A})=100\) and to the optimal constant step \(2/(\lambda_{\max}+\lambda_{\min})\).
7.8 Exercise 8 — Design an experiment (investigation)
You are told a new GNN reaches 94% node-classification accuracy on a citation network, against 89% for GCN.
List everything you would need before believing the method is better. Then design the experiment you would actually run: splits, baselines including a features-only MLP, seeds, how hyperparameters are chosen for both methods, and what you would report. Finally, state the result that would convince you the graph itself is not helping.
8 What to take away
- Expectation is linear unconditionally; variance adds only for uncorrelated terms. That gap is why estimators can be unbiased yet noisy.
- Degrees in \(G_{np}\) are Binomial, hence approximately Poisson — a tail far too light for real networks.
- A sampled mean is unbiased, but a nonlinearity applied after it removes the guarantee: the layer output and its gradient can be biased.
- Maximum likelihood maximizes \(\sum_i\log p_{\theta}(x_i)\); most losses here are negative log-likelihoods.
- A GCN layer is an MLP layer with one extra matrix, \(\hat{\mathbf{A}}_{\mathrm{sl}}\), that lets nodes see their neighbours. That is this layer, not every GNN.
- Logits are not probabilities.
CrossEntropyLosswants logits, and passing it a softmax applies the softmax twice with no error message. - Sigmoid-with-BCE and softmax-with-CE both give \(\partial\mathcal{L}/\partial\mathbf{z}=\hat{\mathbf{p}}-\mathbf{y}\).
- Backpropagation is the chain rule with the per-layer error signal cached — which is why activations must be held in memory.
- Mini-batch SGD needs uniform sampling of indices, not independent data.
- Convex means every local minimum is global — not that a minimum exists, nor that it is unique. Existence needs \(\mathbf{b}\in\operatorname{range}(\mathbf{A})\); uniqueness needs a positive definite Hessian. Flat directions come from a singular Hessian, and \(\kappa=\infty\) is the signature.
- A result without a baseline, a split you trust, and a spread over seeds is not yet a result.
You are ready for Lecture 1.
References
For more depth: Goodfellow, Bengio and Courville’s Deep Learning (Goodfellow et al. 2016) for the network and backpropagation material; Boyd and Vandenberghe’s Convex Optimization (Boyd and Vandenberghe 2004) for the optimization; and Murphy’s Probabilistic Machine Learning (Murphy 2022) for the probability. Shalev-Shwartz and Ben-David’s Understanding Machine Learning (Shalev-Shwartz and Ben-David 2014) is the natural follow-up for the experimental material.