MAP545 Exam Recap and Correction Guide

Correction summary. A neuron computes an affine score from the inputs, adds a bias, then applies an activation function to produce the output.

What a full-credit answer needed.

• State that the inputs are combined linearly with weights.
• Mention the bias term explicitly.
• Finish with the activation or nonlinearity applied to the score.

Why this answer works. This is the base computation repeated throughout MLPs. The lecture insists that a neuron is not just a weighted sum: without the bias and activation, it is only an affine map and cannot create the nonlinear behavior needed in deep networks.

Key concepts you must know first.

• neuron
• affine map
• activation function
• layered network notation

Relevant revision chapters.

Lecture references.

• Deep Learning Lecture 1, slides 3-44
• Deep Learning Lecture 1, slides 45-91

Correction references.

• Final Optimization.pdf, question 1

Common traps.

• Do not forget the bias term.
• Do not describe backpropagation or training when the question only asks for the forward operation.

Correction summary. The perceptron updates a single linear classifier whenever an example is misclassified or not strictly correctly classified. The canonical update is \(w_{t+1} = w_t + y_i x_i\) when \(y_i \langle w_t, x_i \rangle \le 0\).

What a full-credit answer needed.

• Say that the method is for a single-layer linear threshold classifier.
• State the condition \(y_i \langle w_t, x_i \rangle \le 0\).
• Write the update equation and explain that it moves toward the misclassified sample.

Why this answer works. The course uses the perceptron as the historical bridge between linear classification and later differentiable neural methods. Its update is simple and geometric, but its limitations motivate logistic loss and multilayer training.

Key concepts you must know first.

• perceptron
• linear separability
• margin intuition
• update rule

Relevant revision chapters.

Lecture references.

• Deep Learning Lecture 1, slides 3-44
• Deep Learning Lecture 1, slides 45-91

Correction references.

• Final Optimization.pdf, question 2

Common traps.

• Do not present the perceptron as a deep-network training algorithm.
• Do not omit the misclassification condition.

Correction summary. The input layer size follows the input representation, while the output layer size and activation follow the target structure: linear for regression, sigmoid for binary outputs, softmax for multiclass outputs.

What a full-credit answer needed.

• Tie the input dimension to the number or structure of input variables.
• Tie the output dimension to the prediction target.
• Name the matching output activation for regression, binary classification, and multiclass classification.

Why this answer works. This question tests whether the student connects architecture to task semantics. The lecture repeatedly emphasizes that the last layer is chosen from the target type, not from arbitrary preference.

Key concepts you must know first.

• input representation
• output unit
• regression vs classification
• softmax

Relevant revision chapters.

Lecture references.

• Deep Learning Lecture 1, slides 3-44
• Deep Learning Lecture 1, slides 45-91
• Deep Learning Lecture 2, slides 8-62

Correction references.

• Final Optimization.pdf, question 3

Common traps.

• Do not answer only with layer sizes; the activation must also be justified.
• Do not use softmax for regression or independent sigmoids as a default multiclass answer.

Correction summary. Backpropagation is an efficient recursive procedure for computing all parameter gradients in a layered network. A naive method would compute each partial derivative separately, requiring one pass per parameter, whereas backpropagation reuses shared chain-rule terms and gets the full gradient in one forward/backward sweep.

What a full-credit answer needed.

• Define backpropagation as gradient computation, not optimization.
• Describe the naive per-parameter approach.
• Explain the computational saving from reusing intermediate derivatives.

Why this answer works. The exam correction is explicit that calling backpropagation an optimizer should receive zero credit. The lectures frame backpropagation as the reason deep networks became trainable at scale: it organizes chain-rule reuse.

Key concepts you must know first.

• backpropagation
• chain rule
• gradient computation
• computational complexity

Relevant revision chapters.

Lecture references.

• Deep Learning Lecture 1, slides 3-44
• Deep Learning Lecture 1, slides 45-91

Correction references.

• Final Optimization.pdf, question 4

Common traps.

• Backpropagation is not GD, SGD, Adam, or any optimizer.
• A vague 'it is faster' answer is incomplete unless you explain reuse of shared computations.

Correction summary. No. The perceptron algorithm is a single-layer, binary, linear-separability method and does not provide the multilayer differentiable training procedure needed for deep networks.

What a full-credit answer needed.

• Say clearly that the perceptron algorithm is not for deep multilayer networks.
• Mention the single-layer or binary nature of the method.
• Mention at least one practical limitation such as lack of convergence on nonseparable data.

Why this answer works. This is a conceptual separation question: the course uses the perceptron for historical intuition, but training deep networks requires differentiable losses plus backpropagation and gradient-based optimization.

Key concepts you must know first.

• perceptron limitations
• deep-network training
• linear separability
• backpropagation

Relevant revision chapters.

Lecture references.

• Deep Learning Lecture 1, slides 3-44
• Deep Learning Lecture 1, slides 45-91

Correction references.

• Final Optimization.pdf, question 5

Common traps.

• Do not say 'yes if the learning rate is small'.
• Do not confuse the perceptron update with generic SGD on differentiable networks.

Correction summary. ReLU is cheap, nonsaturating on the positive side, and often easier to optimize than sigmoid or tanh in hidden layers. Its main drawback is the dead-neuron problem, which can be mitigated with positive biasing or variants such as Leaky ReLU, PReLU, ELU, or Swish-like choices.

What a full-credit answer needed.

• Mention the optimization benefit of nonsaturation on the positive side or computational simplicity.
• Name the dead-neuron issue.
• Give at least one mitigation strategy or activation variant.

Why this answer works. The lecture recommendation is pragmatic: ReLU or Swish are strong defaults, but students must understand why ReLU replaced sigmoid in hidden layers and what can still go wrong during training.

Key concepts you must know first.

• ReLU
• dead neurons
• activation choice
• hidden-layer optimization

Relevant revision chapters.

Lecture references.

• Deep Learning Lecture 2, slides 8-62
• Deep Learning Lecture 2, slides 63-124

Correction references.

• Final Optimization.pdf, question 6

Common traps.

• Do not say ReLU solves vanishing gradients completely.
• Do not give only the benefit or only the drawback.

Correction summary. In deep feedforward networks, gradients with respect to early-layer parameters can become much smaller than those for later layers because repeated multiplication by derivatives smaller than one shrinks the signal backward through the network.

What a full-credit answer needed.

• Locate the issue in deep layered networks.
• Explain that repeated derivative multiplication causes shrinkage.
• State the consequence: early layers learn slowly or become hard to train.

Why this answer works. The correction expects the ANN version of vanishing gradients here. The RNN-specific version appears later and must be distinguished from this one.

Key concepts you must know first.

• vanishing gradient in ANN
• chain rule
• activation derivatives
• training depth

Relevant revision chapters.

Lecture references.

• Deep Learning Lecture 2, slides 8-62
• Deep Learning Lecture 2, slides 63-124

Correction references.

• Final Optimization.pdf, question 7

Common traps.

• Do not answer with the RNN-specific time-step explanation here.
• Do not say the whole gradient literally becomes zero everywhere.

Correction summary. Not in gradient-based neural-network training: the 0-1 loss is flat almost everywhere and therefore unusable for backpropagation-based optimization.

What a full-credit answer needed.

• State that it cannot be used with gradient-based training.
• Explain that its derivative is zero or undefined almost everywhere.
• Connect this to why surrogate losses are introduced.

Why this answer works. The key lecture point is not merely that 0-1 loss is inconvenient. It is incompatible with the gradient information required by backpropagation and standard optimizers.

Key concepts you must know first.

• 0-1 loss
• surrogate loss
• gradient-based optimization
• backpropagation

Relevant revision chapters.

Lecture references.

• Deep Learning Lecture 2, slides 8-62
• Deep Learning Lecture 2, slides 63-124

Correction references.

• Final Optimization.pdf, question 8

Common traps.

• Do not answer 'for classification only'; the issue is trainability, not label type.
• Do not confuse evaluation metrics with training losses.

Correction summary. During training, dropout samples a binary mask and sets selected neuron outputs to zero, which also zeroes the corresponding gradient flow through those units. At prediction time, the full network is used with the expected-scale correction, classically by multiplying by 1-p or using the inverted-dropout convention during training.

What a full-credit answer needed.

• Explain the random masking at training time.
• Mention that dropped neurons contribute zero output and zero local gradient.
• Explain the train/test difference and the scaling correction.

Why this answer works. The corrected exam is very specific about train/test distinction, so a strong answer must name both phases. The lecture treats dropout as stochastic model averaging and a practical regularizer against co-adaptation.

Key concepts you must know first.

• dropout
• train/test behavior
• regularization
• masking

Relevant revision chapters.

Lecture references.

• Deep Learning Lecture 2, slides 8-62
• Deep Learning Lecture 2, slides 63-124

Correction references.

• Final Optimization.pdf, question 9

Common traps.

• Do not describe dropout as deleting weights permanently.
• Do not forget the prediction-time scaling or the inverted-dropout equivalent.

Correction summary. Valid answers from the lectures include dropout, batch normalization, early stopping, penalization, and weight clipping.

What a full-credit answer needed.

• List any four distinct regularization methods seen in the course.
• Avoid duplicates or vague phrases such as 'data tricks' without a concrete method.

Why this answer works. This looks easy but still checks whether the student has a mental map of training-time regularization tools. The lecture covers both explicit penalties and procedural regularizers.

Key concepts you must know first.

• regularization
• dropout
• batch normalization
• early stopping
• penalization

Relevant revision chapters.

Lecture references.

• Deep Learning Lecture 2, slides 8-62
• Deep Learning Lecture 2, slides 63-124

Correction references.

• Final Optimization.pdf, question 10

Common traps.

• Do not list optimizer names as regularization methods.
• Do not confuse architectural choices with regularizers unless the lecture framed them that way.

Correction summary. Yes in principle, but MLPs ignore spatial locality and translation structure, require far more parameters, and cannot reuse the same local detector across locations the way CNNs do.

What a full-credit answer needed.

• Say that MLPs are possible in principle.
• Explain the loss of spatial inductive bias.
• Mention parameter explosion or lack of weight sharing.

Why this answer works. The lecture frames CNNs as a better match to image structure, not merely as a fashionable alternative. Weight sharing and local receptive fields are the decisive arguments.

Key concepts you must know first.

• CNN vs MLP
• weight sharing
• spatial locality
• image structure

Relevant revision chapters.

Lecture references.

• Deep Learning Lecture 3, slides 6-98
• Deep Learning Lecture 3, slides 99-126

Correction references.

• Final Optimization.pdf, question 11

Common traps.

• Do not answer 'no' absolutely.
• Do not justify only with performance folklore; tie the answer to image structure and parameter count.

Correction summary. The ranking is Dense > Convolutional > Pooling. Dense layers connect every input to every output, convolutional layers have sparse local connectivity with weight sharing, and pooling layers have no trainable parameters.

What a full-credit answer needed.

• Give the correct ranking.
• Justify dense layers with full connectivity.
• Justify convolution with local sparse connections and shared filters.
• State that pooling has no trainable parameters.

Why this answer works. This is a classic comparison question. The answer needs both ranking and structural reason, otherwise the student is only memorizing the order.

Key concepts you must know first.

• dense layer
• convolutional layer
• pooling layer
• parameter count

Relevant revision chapters.

Lecture references.

• Deep Learning Lecture 3, slides 6-98
• Deep Learning Lecture 3, slides 99-126

Correction references.

• Final Optimization.pdf, question 12

Common traps.

• Do not say pooling has 'few' parameters; it has none in the lecture treatment.
• Do not ignore weight sharing when comparing dense and convolutional layers.

Correction summary. A convolutional layer has trainable filters while a pooling layer does not, and convolution spans the full input depth whereas pooling is applied independently within each feature map.

What a full-credit answer needed.

• State the trainable-parameter difference.
• State the difference in how depth or channels are handled.

Why this answer works. The lecture uses this comparison to prevent the common mistake of treating pooling as just another learned filter bank. Pooling is fixed local summarization, not learned feature extraction.

Key concepts you must know first.

• convolution
• pooling
• trainable parameters
• channel handling

Relevant revision chapters.

Lecture references.

• Deep Learning Lecture 3, slides 6-98
• Deep Learning Lecture 3, slides 99-126

Correction references.

• Final Optimization.pdf, question 13

Common traps.

• Do not compare them only by output size reduction; that misses the main conceptual difference.
• Do not claim pooling learns kernels.

Correction summary. Flatten reshapes a tensor-valued representation into a one-dimensional vector without changing the underlying values. It has no parameters and is typically used before dense classifier layers.

What a full-credit answer needed.

• Describe flattening as reshaping, not feature computation.
• State that it has zero trainable parameters.
• Place it before dense layers at the end of many CNN pipelines.

Why this answer works. The layer is easy to overlook because it is structurally simple, but the exam asks it precisely because students often confuse reshaping with learned transformation.

Key concepts you must know first.

• flatten layer
• tensor to vector
• dense classifier head

Relevant revision chapters.

Lecture references.

• Deep Learning Lecture 3, slides 6-98
• Deep Learning Lecture 3, slides 99-126

Correction references.

• Final Optimization.pdf, question 14

Common traps.

• Do not say flatten performs pooling or convolution.
• Do not assign parameters to a pure reshape operation.

Correction summary. The corrected mapping is AlexNet -> split computations across two GPUs, ResNet -> shortcut connections, GoogLeNet -> 1x1 convolutions to reduce computation, ZFNet -> deconvnet to inspect feature maps, and Xception -> depthwise/spatially separated convolutions.

What a full-credit answer needed.

• Provide the five associations correctly.
• Recognize that some of these are architecture signatures rather than generic CNN facts.

Why this answer works. This is a recognition question rather than a derivation question. In the current lecture-backed synthesis, AlexNet, GoogLeNet, and ResNet are clearly covered; Xception and the exact ZFNet deconvnet emphasis are not equally explicit, so they need flagging on the recap page.

Key concepts you must know first.

• CNN architecture signatures
• AlexNet
• GoogLeNet
• ResNet
• Xception
• ZFNet

Relevant revision chapters.

Lecture references.

• Deep Learning Lecture 3, slides 6-98
• Deep Learning Lecture 3, slides 99-126

Correction references.

• Final Optimization.pdf, question 15

Common traps.

• Do not swap ResNet and GoogLeNet.
• Do not treat deconvnet visualization as a generic property of every CNN architecture.

Correction summary. Segmentation assigns a label to each pixel, whereas object detection predicts labeled bounding boxes around objects.

What a full-credit answer needed.

• Define segmentation at pixel level.
• Define detection with bounding boxes.
• Optionally note that segmentation is usually the finer-grained task.

Why this answer works. This item appears in the correction but is not part of the current lecture-backed CNN synthesis. It should therefore be treated as exam-side material rather than retrofitted into the lecture content.

Key concepts you must know first.

• segmentation
• object detection
• pixel-wise prediction
• bounding boxes

Relevant revision chapters.

Lecture references.

• Deep Learning Lecture 3, slides 6-98
• Deep Learning Lecture 3, slides 99-126

Correction references.

• Final Optimization.pdf, question 16

Common traps.

• Do not say both tasks simply 'classify images'.
• Do not confuse localization with pixel-wise labeling.

Correction summary. The corrected answer targets object detection with bounding boxes, labels, and confidence scores. The highlighted improvement is end-to-end prediction of localization and class information in one pipeline instead of separate proposal and classification stages.

What a full-credit answer needed.

• Identify YOLO as an object-detection method.
• Mention bounding boxes plus class probabilities.
• Explain the end-to-end improvement over older two-stage pipelines.

Why this answer works. As with segmentation, this is correction-side exam material rather than lecture-backed course content in the current site. The recap should explain the corrected answer while clearly flagging the scope difference.

Key concepts you must know first.

• YOLO
• object detection
• end-to-end pipeline
• bounding boxes

Relevant revision chapters.

Lecture references.

• Deep Learning Lecture 3, slides 6-98
• Deep Learning Lecture 3, slides 99-126

Correction references.

• Final Optimization.pdf, question 17

Common traps.

• Do not describe YOLO as a segmentation model.
• Do not answer only with 'it is faster' without naming the end-to-end change.

Correction summary. Yes. One can stack recurrent layers, and a standard hidden-state update is \(h_{t+1} = \tanh(W_{HH} h_t + W_{IH} x_{t+1} + b)\).

What a full-credit answer needed.

• Say that multi-layer RNNs are possible.
• Distinguish the number of recurrent layers from the hidden-state dimension.
• Write the regular recurrent update equation.

Why this answer works. The correction emphasizes two distinct ideas: stacking recurrent layers is allowed, and the hidden-state equation itself must be known. Leaving out the recurrence loses the core of the question.

Key concepts you must know first.

• RNN recurrence
• hidden state
• stacked RNN
• tanh update

Relevant revision chapters.

Lecture references.

• Deep Learning Lecture 4, slides 3-58
• Deep Learning Lecture 4, slides 59-77

Correction references.

• Final Optimization.pdf, question 18

Common traps.

• Do not confuse hidden-state size with number of layers.
• Do not answer with an LSTM or GRU equation when regular RNN is requested.

Correction summary. In RNNs, the key issue is that contributions from early time steps in the gradient decomposition become extremely small after repeated Jacobian products, so long-term dependencies are not learned well.

What a full-credit answer needed.

• Distinguish the recurrent version from the feedforward version.
• Explain that early-time contributions become negligible.
• Connect the effect to forgetting long-range dependencies.

Why this answer works. The corrected exam is careful here: it does not say every gradient component is globally near zero. It says the terms linked to early sequence positions vanish inside the temporal sum/product structure.

Key concepts you must know first.

• vanishing gradient in RNNs
• BPTT
• long-term dependencies
• repeated Jacobians

Relevant revision chapters.

Lecture references.

• Deep Learning Lecture 4, slides 3-58
• Deep Learning Lecture 4, slides 59-77

Correction references.

• Final Optimization.pdf, question 19

Common traps.

• Do not reuse the feedforward-layer explanation unchanged.
• Do not say the gradient is identically zero everywhere.

Correction summary. TBPTT breaks a long sequence into shorter subsequences, computes the loss and backpropagation on those windows, and updates recurrent parameters incrementally. It reduces computation and memory per update but worsens the ability to capture very long dependencies.

What a full-credit answer needed.

• Define TBPTT as windowed or truncated backpropagation through time.
• Name the computational benefit.
• Name the long-term-memory drawback.

Why this answer works. This answer is strongest when it balances both sides: TBPTT is not just an approximation trick, it is a practical response to long sequences, with a real cost in temporal credit assignment.

Key concepts you must know first.

• TBPTT
• RNN training
• sequence windows
• long-term dependencies

Relevant revision chapters.

Lecture references.

• Deep Learning Lecture 4, slides 3-58
• Deep Learning Lecture 4, slides 59-77

Correction references.

• Final Optimization.pdf, question 20

Common traps.

• Do not define TBPTT only as 'using mini-batches'.
• Do not ignore the drawback in a question that explicitly asks for one.

Correction summary. SGD starts from an initial point, samples one observation or a mini-batch at each iteration, forms an unbiased gradient estimate, and updates the parameter vector with a learning-rate-scaled step in the negative estimated-gradient direction.

What a full-credit answer needed.

• Mention random sampling of one data point or a mini-batch.
• State the gradient-based update rule.
• Mention the learning rate or step size.

Why this answer works. The corrected exam writes a simplified update, but the lecture-backed version is the finite-sum stochastic update based on sampled gradient estimates. The recap should keep the lecture's more precise formulation.

Key concepts you must know first.

• SGD
• mini-batch
• unbiased gradient estimate
• learning rate

Relevant revision chapters.

Lecture references.

• Optimization Lecture 1, slides 17-24
• Optimization Lecture 1, slides 30-56
• Optimization Lecture 2, slides 4-33

Correction references.

• Final Optimization.pdf, question 21

Common traps.

• Do not describe SGD as using the full gradient at every step.
• Do not forget the role of random sampling.

Correction summary. The local first-order Taylor model shows that -grad f is the direction that decreases the linear approximation most rapidly. The corrected exam expects convexity plus differentiability language; the lecture notes also tie usable step-size guarantees to smoothness.

What a full-credit answer needed.

• Explain the first-order or steepest-descent intuition for -grad f.
• Mention convexity as the global-geometry assumption highlighted in the correction.
• Mention differentiability, and note that smoothness is what the lecture uses for standard consistency and rate proofs.

Why this answer works. This is one of the places where the corrected answer is shorter than the lecture treatment. A strong recap answer should reconcile them: convexity explains why local descent supports global minimization, while smoothness controls the step size and descent guarantee.

Key concepts you must know first.

• gradient descent intuition
• Taylor approximation
• convexity
• smoothness

Relevant revision chapters.

Lecture references.

• Optimization Lecture 1, slides 17-24
• Optimization Lecture 1, slides 30-56
• Optimization Lecture 2, slides 4-33

Correction references.

• Final Optimization.pdf, question 22

Common traps.

• Do not state a convergence rate without assumptions.
• Do not reduce the answer to 'because the gradient points uphill' without the linearization argument.

Correction summary. If \(\rho^{200} = 10^{-3}\), then reaching \(10^{-9}\) requires \(\rho^{600} = 10^{-9}\), so the total is 600 iterations and the additional number required is 400.

What a full-credit answer needed.

• Translate the first fact into \(\rho^{200} = 10^{-3}\).
• Solve \(\rho^k = 10^{-9}\) to get k = 600.
• Answer the actual question with 400 more iterations, not just the total.

Why this answer works. This is a pure reasoning-pattern question about linear rates: equal iteration blocks multiply the error by equal factors. The key is to separate total iterations from additional iterations.

Key concepts you must know first.

• linear convergence
• rate interpretation
• error reduction blocks

Relevant revision chapters.

Lecture references.

• Optimization Lecture 1, slides 17-24
• Optimization Lecture 1, slides 30-56
• Optimization Lecture 2, slides 4-33
• Optimization Lecture 2, slides 34-70

Correction references.

• Final Optimization.pdf, question 23

Common traps.

• Do not answer 600 without noticing the wording 'how many more'.
• Do not treat \(10^{-9}\) as three times smaller than \(10^{-3}\); it is a multiplicative power relation.

Correction summary. A valid lecture-backed answer is SAG, SAGA, or SVRG on strongly convex finite-sum objectives. The corrected exam gives \(\rho = 1 - \min(\mu, 1/n)\) for the cited SAG-type rate.

What a full-credit answer needed.

• Name a variance-reduced algorithm such as SAG, SAGA, or SVRG.
• State the function class: strongly convex finite-sum objectives.
• Give the requested contraction factor if citing the corrected SAG expression.

Why this answer works. The point of the question is not to memorize one acronym. It is to connect linear convergence with the right algorithm family and assumptions.

Key concepts you must know first.

• variance reduction
• SAG
• SVRG
• SAGA
• strong convexity
• linear rate

Relevant revision chapters.

Lecture references.

• Optimization Lecture 2, slides 34-70
• Optimization Lecture 3, slides 1-46

Correction references.

• Final Optimization.pdf, question 24

Common traps.

• Do not give Newton here unless you also specify the setting the course used for the stated rate form.
• Do not omit strong convexity.

Correction summary. Because SGD uses noisy gradient estimates, the step size is decreased over time to reduce stochastic noise and stabilize convergence. The correction gives \(\gamma_t = 1/\sqrt{t}\) for smooth convex objectives and \(\gamma_t\) = \(1/t\) for strongly convex ones.

What a full-credit answer needed.

• Explain the noise-reduction intuition for decreasing step sizes.
• State the typical convex schedule \(1/\sqrt{t}\).
• State the strongly convex schedule \(1/t\).

Why this answer works. The lecture frames step-size decay as the price paid for stochasticity: large early steps aid progress, but smaller later steps prevent persistent noise from dominating.

Key concepts you must know first.

• SGD step size
• stochastic noise
• convex vs strongly convex schedules

Relevant revision chapters.

Lecture references.

• Optimization Lecture 1, slides 17-24
• Optimization Lecture 1, slides 30-56
• Optimization Lecture 2, slides 4-33

Correction references.

• Final Optimization.pdf, question 25

Common traps.

• Do not give a constant step size as the textbook answer to this exam question.
• Do not omit the intuition behind decay.

Correction summary. Poor conditioning means the curvature is very anisotropic: the largest Hessian eigenvalue is much bigger than the smallest. For smooth strongly convex problems the condition number is kappa = L / mu. The corrected exam highlights Newton's method and momentum-based methods as the main remedies.

What a full-credit answer needed.

• Explain conditioning geometrically or spectrally.
• Give the mathematical definition of the condition number.
• Name Newton and momentum as the two emphasized remedies.

Why this answer works. This question checks both conceptual and algorithmic understanding. The important link is that elongated geometry slows first-order descent, which motivates curvature-aware or momentum-accelerated methods.

Key concepts you must know first.

• conditioning
• eigenvalues
• condition number
• Newton
• momentum

Relevant revision chapters.

Lecture references.

• Optimization Lecture 1, slides 17-24
• Optimization Lecture 1, slides 30-56
• Optimization Lecture 2, slides 4-33
• Optimization Lecture 2, slides 34-70

Correction references.

• Final Optimization.pdf, question 26

Common traps.

• Do not define conditioning only qualitatively without the ratio.
• Do not say SGD is the specific remedy for poor conditioning; the lecture emphasizes momentum or Newton-type ideas.

Correction summary. The cleaned comparison is: rates \(1/k\) for GD and \(1/\sqrt{k}\) for SGD; per-iteration costs O(nd) for GD and O(d) for SGD; to reach precision \(n^{-1/4}\) the iteration counts are \(n^{1/4}\) for GD and \(n^{1/2}\) for SGD, giving total costs \(n^{5/4}\) d and \(n^{1/2}\) d; to reach precision \(n^{-3}\) the iteration counts are \(n^3\) for GD and \(n^6\) for SGD, giving total costs \(n^4\) d and \(n^6\) d.

What a full-credit answer needed.

• State both convergence rates.
• State both per-iteration costs.
• Compute the iteration and total-cost consequences at the two target precisions.

Why this answer works. The point is to separate rate from actual computational complexity. A slower rate can still win for modest precision because its iterations are much cheaper.

Key concepts you must know first.

• GD vs SGD
• rate vs complexity
• target precision
• finite-sum cost model

Relevant revision chapters.

Lecture references.

• Optimization Lecture 1, slides 17-24
• Optimization Lecture 1, slides 30-56
• Optimization Lecture 2, slides 4-33

Correction references.

• Final Optimization.pdf, question 27

Common traps.

• Do not leave the answer at the rate line only; the table is about total complexity.
• Do not mix the two target precision regimes.

Correction summary. SGD is computationally preferable for low-precision optimization, while GD becomes preferable when very high precision is needed. In machine learning, moderate precision is usually enough because the empirical objective itself is only an estimate of the true risk.

What a full-credit answer needed.

• Contrast low-precision and high-precision regimes.
• Say explicitly that ML often lives in the low-to-moderate precision regime.

Why this answer works. This question is the interpretation step after the table. The exam rewards the student who explains what the numbers mean for practice rather than repeating the numbers themselves.

Key concepts you must know first.

• optimization precision
• GD vs SGD tradeoff
• statistical accuracy vs optimization accuracy

Relevant revision chapters.

Lecture references.

• Optimization Lecture 1, slides 17-24
• Optimization Lecture 1, slides 30-56
• Optimization Lecture 2, slides 4-33

Correction references.

• Final Optimization.pdf, question 28

Common traps.

• Do not say SGD is always better.
• Do not ignore the statistical-precision argument from ML.

Correction summary. Nesterov acceleration adds momentum by combining the current step with information from previous descent directions, creating a look-ahead or velocity effect. It remains a first-order method because it uses gradients, not Hessians.

What a full-credit answer needed.

• Explain the momentum or look-ahead idea.
• Classify NAG as first-order.

Why this answer works. The correction expects a sentence-level intuition, not only the update formula. Students must state both the momentum idea and the first-order classification.

Key concepts you must know first.

• Nesterov acceleration
• momentum
• first-order methods

Relevant revision chapters.

Lecture references.

• Optimization Lecture 2, slides 34-70
• Optimization Lecture 3, slides 1-46

Correction references.

• Final Optimization.pdf, question 29

Common traps.

• Do not call NAG a second-order method.
• Do not say only 'it is faster' without the momentum intuition.

Correction summary. Variance-reduced methods reuse previously computed gradient information to reduce stochastic noise while keeping per-iteration cost close to stochastic methods. Valid examples in the lectures include SAG, SAGA, and SVRG.

What a full-credit answer needed.

• Explain that the goal is to reduce the variance of stochastic gradients.
• Name a valid algorithm such as SAG, SAGA, or SVRG.
• Describe at a high level how past or reference gradients are reused.

Why this answer works. A complete answer must connect the algorithm family to the problem it solves: noisy stochastic directions in finite-sum optimization. The correction is short here, so the recap should add lecture-grounded algorithm intuition.

Key concepts you must know first.

• variance reduction
• gradient memory
• finite-sum optimization
• SAG
• SVRG
• SAGA

Relevant revision chapters.

Lecture references.

• Optimization Lecture 2, slides 34-70
• Optimization Lecture 3, slides 1-46

Correction references.

• Final Optimization.pdf, question 30

Common traps.

• Do not describe variance reduction as momentum.
• Do not name an algorithm without stating how it uses stored or reference gradient information.

Correction summary. SVRG uses much less memory than SAG because it does not store one gradient per sample, but it pays a higher computational price per update because it uses two gradient evaluations around the reference-point correction.

What a full-credit answer needed.

• Give the memory advantage of SVRG.
• Give the cost-per-update drawback relative to SAG.

Why this answer works. This question tests whether the student can compare two methods in the same family by concrete computational tradeoffs rather than abstract praise.

Key concepts you must know first.

• SVRG
• SAG
• memory complexity
• per-iteration cost

Relevant revision chapters.

Lecture references.

• Optimization Lecture 2, slides 34-70
• Optimization Lecture 3, slides 1-46

Correction references.

• Final Optimization.pdf, question 31

Common traps.

• Do not compare them only by convergence rate.
• Do not forget which method stores a gradient table.

Correction summary. Newton's update is \(w_{t+1} = w_t - (\nabla^2 f(w_t))^{-1} \nabla f(w_t)\). For quadratic objectives with positive-definite Hessian, the local quadratic model is exact, so Newton reaches the minimizer in one step from any starting point where the Hessian is invertible.

What a full-credit answer needed.

• Write the Newton update equation.
• State the one-step property on quadratic objectives.
• Justify it by the exactness of the quadratic model or constant Hessian.

Why this answer works. The exam correction works out the quadratic case explicitly. A strong answer on the recap page should preserve the logic: exact curvature makes the Newton step solve the problem immediately.

Key concepts you must know first.

• Newton's method
• Hessian inverse
• quadratic objective
• one-step convergence

Relevant revision chapters.

Lecture references.

• Optimization Lecture 2, slides 34-70
• Optimization Lecture 3, slides 1-46

Correction references.

• Final Optimization.pdf, question 32

Common traps.

• Do not omit the Hessian inverse.
• Do not claim one-step convergence for arbitrary nonquadratic objectives.

Correction summary. The functions \(f_i\) correspond to the loss contributions of individual observations. A natural example is training a deep neural network with many parameters on a large data set, giving large d, large n, nonconvexity, and nonsmoothness with ReLU-type components. Under that regime, the corrected exam's ranking is RMSprop first, SAGA second, and LBFGS third, with the rationale that adaptive stochastic methods fit large-scale deep training better than memory-heavy or second-order-style methods.

What a full-credit answer needed.

• Identify \(f_i\) as the loss attached to the i-th observation.
• Give a concrete example with large n and d, plus nonconvex and nonsmooth structure.
• Rank the three methods and justify the ranking by regime fit, not by generic prestige.

Why this answer works. This is the most synthesis-heavy question in the exam. The ranking is scenario-dependent: the correction's order makes sense for large-scale deep learning, but the recap should state clearly that the justification matters more than pretending the ranking is universal.

Key concepts you must know first.

• finite-sum objectives
• deep-learning optimization regime
• LBFGS
• RMSprop
• SAGA
• algorithm selection

Relevant revision chapters.

Lecture references.

• Optimization Lecture 1, slides 17-24
• Optimization Lecture 2, slides 34-70
• Optimization Lecture 3, slides 47-77

Correction references.

• Final Optimization.pdf, question 33

Common traps.

• Do not define \(f_i\) as a feature or a neuron.
• Do not present the ranking as universal across all optimization problems.