Adversarial Examples, Automatic Differentiation and Robust Generalisation

Three ideas make this question easy:

1. a linear classifier is just a line with an arrow,
2. an \(\ell_\infty\) budget is a square around the point,
3. the attack steps along the sign of the gradient, then clips back into the square.

Each gets a short primer below. Then we solve the question live.

The classifier's score is

It is zero on a line, the decision boundary:

Points on one side have \(f > 0\) and are Class 1. Points on the other side are Class 2.

The gradient of a linear function is the same everywhere:

This arrow is perpendicular to the boundary and points into Class 1. So "increase \(f\)" always means "move along \(W\)", wherever you start. That is why one step of the attack will be enough.

How far is the boundary? It depends on how you measure distance (lecture 16, slides 6–8):

The \(\ell_2\) path goes straight along \(W\). The \(\ell_\infty\) path moves every coordinate by the same amount. Section 1.2 explains why.

An attack may move the input by a perturbation \(\delta\), but only within a budget \(\epsilon\) (lecture 16, slides 10–11):

Three common ways to measure the size of \(\delta\):

The \(\ell_\infty\) ball is a square. Every coordinate may change by up to \(\epsilon\), independently. For images: no pixel changes by more than \(\epsilon\).

Which \(\delta\) pushes a linear score up the most? Inside the square, the answer is always a corner:

That corner is exactly the FGSM step.

FGSM takes one big step of size \(\epsilon\) (lecture 16, slide 15):

Iterative FGSM takes several smaller steps of size \(\alpha\). After each step it projects back into the budget (slide 17):

For \(\ell_\infty\), the projection simply clips each coordinate back into its allowed interval:

Small steps matter when the boundary is curved, where one big step can overshoot (slide 16). The animation at the top of the page shows that case.

Which direction? At the starting point,

To reach Class 1 we must increase \(f\), so we step along \(+\operatorname{sign}(\nabla f)\).

Bridge to Q1. Q1 is the same computation with \(W = [2, -1]\), \(b = 0.5\), a step of \(\alpha = 1\) and a budget of \(\epsilon = 3\). The only new ingredient is that the step is repeated, with a projection after each step.

The missing layer simply subtracts:

The official answer writes \(b_0 - b_1\), counting from zero.

A function with \(n\) inputs and \(m\) outputs has an \(m \times n\) matrix of derivatives, its Jacobian (lecture 17, slide 21):

For a single scalar output, the Jacobian is one row: the gradient.

For a chain of layers, the chain rule multiplies the layer Jacobians:

Cost of one product. An \((m\times n)\) matrix times an \((n\times p)\) matrix has \(m p\) entries, each a sum of \(n\) products:

The key point. Matrix products are associative, so we may bracket the chain either way. That choice is the difference between the two modes:

Each node stores its value from the forward pass. Each edge carries a local derivative. Lecture 17's rule (slide 18):

• Forward mode pushes derivatives with respect to one input from left to right. One sweep per input.
• Reverse mode pulls the derivative of the output from right to left. One sweep per output.

The two update rules, written out. A tangent \(\dot v\) is a derivative with respect to the seeded input, and flows forward:

An adjoint \(\bar v\) is the derivative of \(y\) with respect to \(v\), and flows backward:

Bridge to Q2. Q2 has the opposite shape: two inputs and one output. So expect reverse mode to win there.

Directly. Differentiating by hand gives two partial derivatives:

Layer by layer. First the three Jacobians, then the two ways of multiplying them. Switch to numbers to see the values at \((2, 4)\).

(a) Operation count and other computational costs

Forward mode needs 16 multiplications, reverse mode 12.

Other costs:

• Memory. Reverse mode must keep every layer's values from the forward pass until the backward pass reaches them (the "tape"). Forward mode can discard each Jacobian once it has been used.
• Additions inside each dot product.
• Evaluating each elementary derivative.

The last item is cheap, because autodiff looks up derivatives of elementary functions (the derivative of \(\cos\) is \(-\sin\), and so on). Once derivatives are lookups, the remaining work is combining them, and that is dominated by the multiplications.

(b) Non-elementary functions in the partition

The table knows the derivative of \(\cos(u)\) for a single input \(u\). It does not know the derivative of \(\cos(a_2 + a_3)\) as a function of two inputs.

The fix: add a layer that forms the sum first,

The next layer then applies \(\cos\) and \(\sin\) to one input each.

(c) An operation-reducing partition

Fold the subtraction into \(g\):

Now \(g_{\mathbf a}\) is \(1\times3\), and reverse mode costs

Compare all four partitions below.

This question ties the first two together:

• adversarial training runs the attack from Q1 inside every training step,
• and computes all its gradients with the reverse mode from Q2.

The generalisation gap compares performance on the training data with performance on unseen test data:

The robust accuracy counts a point as correct only if every perturbation inside its budget is still classified correctly. In practice we check this with a strong attack such as PGD:

That gives a second gap:

A standard train/test split assumes both sets come from the same distribution. Attackers, and real deployments, break that assumption.

Instead of minimising the loss at each training point, minimise it at the worst point in that point's \(\epsilon\)-box⁴:

• The inner max is approximated by PGD: the loop from Q1, with a random start.
• The outer min is ordinary gradient descent on the weights \(\theta\), using reverse mode from Q2.

Same graph, two targets: the attack differentiates with respect to the input, training with respect to the weights (lecture 17, slide 17).

The catch. Each training point now asks for a whole box to be classified correctly, not just one point. A flexible model can fit those boxes exactly. But fitting boxes around 30 points says little about the boxes around new points.

Bridge to Q3. Adversarial training makes the model create that margin around its training points. The next experiment asks whether the margin carries over to test points.

Put the data on a thin manifold, here a horizontal line. The label changes at the middle.

Any boundary through the middle that is not horizontal gets 100% accuracy. But as the boundary tilts towards the data line, every point gets closer to it in directions off the manifold.

Standard training has no reason to prefer an upright boundary. This is the boundary-tilting picture of adversarial examples¹¹.

Implications for learning and decision boundaries

Models fit what they are shown. Adversarial training constrains the boundary only inside the boxes around training points. A flexible model can memorise those boxes, reaching near-100% robust training accuracy, without keeping a margin around new points. This robust overfitting grows with longer training, and early stopping helps⁶.

Robustness needs more data. Robust generalisation can need far more samples than standard generalisation⁵. The experiment shows this when you go from 30 to 120 training points.

Boundaries hug the manifold. Real data lie near a low-dimensional manifold. Standard training only cares that points on it land on the right side. In off-manifold directions the boundary can sit very close to the data (3.5), and adversarial examples exploit exactly those directions^11,12,13.

Accuracy and robustness can pull apart. Forcing the boundary to keep its distance can cost clean accuracy^7,8. Some useful features are real but brittle, and robust training makes the model give them up⁹.