week 3

Question 1

What is the goal of learning/training in ML?

Answer 1

Choose a hypothesis class FΘ and loss l, and find θ̂ = argminθ R̂(θ) such that f_θ̂ predicts labels well.

Question 2

What is empirical risk R̂(θ)?

Answer 2

R̂(θ)= (1/n) Σ_j l(y_j, f_θ(x_j)).

Question 3

Why do we minimise empirical risk?

Answer 3

Because the true risk is unknown; empirical risk approximates it using training data.

Question 4

What does gradient descent rely on?

Answer 4

Local information: the gradient ∇θF gives the steepest direction of increase, so −∇θF is steepest descent.

Question 5

What is a directional derivative?

Answer 5

vᵀ ∇θ F — tells the rate of change of F when moving infinitesimally in direction v.

Question 6

What is a descent direction?

Answer 6

Any v such that vᵀ∇θF < 0, meaning moving along v reduces F.

Question 7

What is the direction of steepest descent?

Answer 7

v = −∇θF / ||∇θF||.

Question 8

What is the gradient descent update rule?

Answer 8

θ_{t+1} = θ_t − γ_t ∇θ_t F.

Question 9

What does γ_t represent in gradient descent?

Answer 9

Learning rate (step size).

Question 10

What is gradient flow?

Answer 10

The continuous-time limit: dθ/dt = −∇θF(θ(t)).

Question 11

How is GD related to gradient flow?

Answer 11

GD is a numerical approximation of gradient flow with step size γ_t.

Question 12

Why does geometry of level sets matter for GD?

Answer 12

Because ∇F is orthogonal to level sets; elongated level sets cause slow convergence.

Question 13

What does the condition number κ measure?

Answer 13

κ = λ_max / λ_min of (1/n)XᵀX; large κ means slow convergence.

Question 14

Why is GD not applicable to 0–1 loss?

Answer 14

Its gradient is zero almost everywhere.

Question 15

What happens if ∇θF = 0?

Answer 15

GD gets stuck (local minimum, saddle point, plateau).

Question 16

How does step size affect GD?

Answer 16

Too small: slow. Too large: divergence or oscillations.

Question 17

What are common learning rate schedules?

Answer 17

Constant γ; diminishing γ_t→0; exponential γ_t = γ₀β^t; line search.

Question 18

What is excess risk decomposition?

Answer 18

R(f̂) − R* = (estimation error) + (approximation error).

Question 19

What is estimation error?

Answer 19

R(f̂) − R(f_{θ*}) — due to finite data.

Question 20

What is approximation error?

Answer 20

R(f_{θ}) − R — due to model class limitations.

Question 21

What is optimisation error?

Answer 21

R̂(f̂) − infθ R̂(fθ) — due to not fully minimising empirical risk.

Question 22

Why is full GD expensive?

Answer 22

Computing ∇θ F requires evaluating all n samples; too slow for large n.

Question 23

What is stochastic gradient descent (SGD)?

Answer 23

θ_{t+1} = θ_t − γ_t ∇θ_t l(y_j, f_θ(x_j)) using one randomly sampled data point.

Question 24

What is the key idea of SGD?

Answer 24

Replace full gradient with unbiased stochastic estimate.

Question 25

Why is SGD not a descent direction?

Answer 25

Because gradient of a single sample can point uphill.

Question 26

What is mini-batch SGD?

Answer 26

Use a batch B_t ⊂ {1,…,n}: θ_{t+1}=θ_t−γ_t (1/|B_t|) Σ_{j∈B_t}∇l_j.

Question 27

What is an epoch?

Answer 27

One full pass through all data using batches.

Question 28

Typical batch sizes?

Answer 28

32–256.

Question 29

What is gradient clipping?

Answer 29

Rescale ∇F → c ∇F/||∇F|| to prevent exploding gradients.

Question 30

What is early stopping?

Answer 30

Stop training when validation risk stops decreasing; acts as implicit regularisation.

Question 31

Why does early stopping regularise?

Answer 31

Parameters remain small early in training, similar to L2 penalty.

Question 32

Why can SGD escape local minima?

Answer 32

Noise helps avoid sharp minima; SGD does not strictly follow descent directions.

Question 33

Why do sharp minima generalise poorly?

Answer 33

They overfit; flatter minima yield better generalisation.

Question 34

What is momentum in optimisation?

Answer 34

θ_{t+1} = θ_t − γ ∇F(θ_t) + β (θ_t − θ_{t−1}).

Question 35

What does momentum do?

Answer 35

Smooths updates and accelerates convergence in shallow directions.

Question 36

Why introduce ADAM?

Answer 36

Different parameters may have different scales; need adaptive per-dimension learning rates.

Question 37

What does ADAM do?

Answer 37

Normalises gradient by its first and second moments: updates use m_t and v_t (momentum terms).

Question 38

Why is ADAM effective?

Answer 38

Makes progress in every direction regardless of gradient scale.

Question 39

What are overparameterised models?

Answer 39

Models with enough parameters to fit the training data exactly (interpolation).

Question 40

Why do overparametrised models overfit?

Answer 40

They can achieve zero empirical risk but fit noise.

Question 41

What is explicit regularisation?

Answer 41

Modify objective: J(θ)=R̂(θ)+λΩ(θ).

Question 42

What is implicit regularisation?

Answer 42

Algorithm biases the solution without modifying objective (e.g., SGD selects minimum-norm interpolator).

Question 43

What is the implicit bias of SGD for linear regression?

Answer 43

Among all interpolating solutions, SGD converges to the minimum Euclidean norm solution.

Question 44

Does implicit regularisation depend on loss?

Answer 44

No — occurs for quadratic and logistic loss.

Question 45

What is the double descent phenomenon?

Answer 45

Test error decreases → increases near interpolation → decreases again in extreme overparameterisation.

Question 46

What causes double descent?

Answer 46

Increased model size induces inductive biases and effective simplicity beyond interpolation threshold.

Question 47

How does GD implicitly regularise?

Answer 47

GD approximates gradient flow of F̃(θ)=F(θ)+γ/4 ||∂F/∂θ||², i.e., penalises large gradients.

Question 48

What is a convex function?

Answer 48

F is convex if F(tη+(1−t)θ) ≤ tF(η)+(1−t)F(θ) for all θ,η and t∈[0,1].

Question 49

What does ∇θF = 0 imply for convex F?

Answer 49

Any stationary point is a global minimum.

Question 50

Do convex functions need to be differentiable?

Answer 50

No — convexity does not require differentiability.

Question 51

How do we optimise non-smooth functions?

Answer 51

Replace gradient with a subgradient z ∈ ∂F(θ).

Question 52

What is a subgradient?

Answer 52

A generalisation of gradient that exists for convex functions even if non-smooth.

Question 53

What is the GD update with subgradients?

Answer 53

θ_{t+1} = θ_t − γ z_t, where z_t ∈ ∂F(θ_t).