MAP545 Revision Site

Optimization Extensions I: Acceleration, Variance Reduction, and Newton-Type Methods

Optimization Extensions I

← DL Foundations Back to Index DL Training and Regularization →

Chapter Overview

This chapter studies the first major upgrades to GD and SGD. The lecture sequence moves from momentum-based acceleration, to variance-reduced stochastic methods for finite sums, to second-order and quasi-second-order methods.

It matters because the course repeatedly asks the same meta-question: which weakness of the baseline method is being corrected? Momentum addresses poor conditioning and directional inertia. Variance reduction addresses the noise floor of SGD. Newton-type methods address curvature directly.

These methods are not presented as an unstructured list. They form a taxonomy: first-order deterministic, first-order stochastic, accelerated, variance-reduced, second-order, and quasi-Newton. The exam expects you to recognize these categories and explain the benefit and drawback of each.

Important Definitions

  • Momentum / Heavy Ball (HB). Add a fraction of the previous displacement to the current gradient step.
  • Nesterov accelerated gradient (NAG). Apply the momentum shift first, then compute the gradient at the look-ahead point.
  • Variance-reduced methods. Stochastic methods for finite-sum objectives that reuse past gradient information to reduce gradient noise.
  • SAG. Stochastic Average Gradient: stores one past gradient per data point and uses their average.
  • SVRG. Stochastic Variance Reduced Gradient: alternates outer loops computing a full gradient at an anchor point and inner-loop corrections around that anchor.
  • Newton method. Second-order method using the inverse Hessian times the gradient.
  • Quasi-Newton method. Approximate the Newton direction using only first-order information and low-rank Hessian approximations.

Key Concepts and Intuition

  • Acceleration is about memory of direction. If successive gradients point roughly the same way, throwing away past motion is wasteful. Momentum methods retain this consistency and can traverse badly conditioned valleys faster.
  • NAG is more than "momentum with a different name". The lecture emphasizes the look-ahead point: the gradient is evaluated after the momentum move, which produces the stronger theoretical guarantees.
  • Variance reduction tries to get the best of GD and SGD. The objective is to keep cheap iterations while removing the persistent noise that prevents high-accuracy convergence for vanilla SGD.
  • Second-order methods use curvature rather than just slope. Newton's direction minimizes the local quadratic model, not just the linear approximation.
  • Quasi-Newton methods are compromise methods. They give up exact Hessians to reduce cost from cubic to quadratic in the dimension while still mimicking curvature.

Mathematical Content

Heavy Ball / Polyak momentum.

\[\theta_{t+1} = \theta_{t} - \eta_{t}\nabla f(\theta_{t}) + \beta_{t}(\theta_{t} - \theta_{t-1})\]

Nesterov accelerated gradient.

\[ζ_{t} = \theta_{t} + \beta_{t}(\theta_{t} - \theta_{t-1})\]
\[\theta_{t+1} = ζ_{t} - \eta_{t}\nabla f(ζ_{t})\]

NAG rates highlighted in the lecture.

\[If f is L-smooth and convex, with \eta \le 1/L and \beta_{t+1} = t / (t + 3), then f(\theta_{t}) - f(\theta^*) \le 2\|\theta_{0} - \theta^*\|^{2} / (\eta(t+1)^{2})\]
\[If f is L-smooth and \mu-strongly convex, choose \eta = 1/L and \beta = (1 - \sqrt{\mu/L}) / (1 + \sqrt{\mu/L}); then the rate improves to a linear contraction \in \sqrt{\mu/L}\]

Variance reduction for finite sums.

\[f(\theta) = (1/n) \sum_{i=1}^{n} f_{i}(\theta)\]
\[\text{SAG update:} \theta_{t+1} = \theta_{t} - (\eta/n) \sum_{i=1}^{n} g_{i,t}\]

Each gi,t is the latest stored gradient for sample i. The update cost is SGD-like, but memory is O(nd).

\[\text{SVRG inner update:} \theta_{t,k+1} = \theta_{t,k} - \eta( \nabla f_{i}(\theta_{t,k}) - \nabla f_{i}(\theta_{t,0}) + \nabla f(\theta_{t,0}) )\]

SVRG reduces memory to O(d), but every inner step uses two sample gradients plus the periodically recomputed full gradient at the anchor point.

\[\text{SAGA theorem slide:} \mathbb{E}[f(\theta_{T}) - f(\theta^*)] contracts geometrically under L-smoothness and \mu-strong convexity with constant step size\]

Newton method.

\[\theta_{t+1} = \theta_{t} - ( \nabla^{2}f(\theta_{t}) )^{-1}\nabla f(\theta_{t})\]

The lecture interprets this as the exact minimizer of the local quadratic approximation. On quadratic functions, this approximation is exact everywhere, so Newton reaches the minimizer in one step from any starting point when the Hessian is invertible and positive definite.

\[If f(\theta) = (1/2)\theta^{T}A\theta + b^{T}\theta + c, then \theta^* = -A^{-1}b and Newton produces \theta_{1} = \theta^*\]

Near a solution of a smooth strongly convex function with Lipschitz Hessian, Newton has local quadratic convergence: the error is essentially squared at each step.

Quasi-Newton logic.

\[\theta_{t} = \theta_{t-1} - \eta_{t-1}B_{t-1}^{-1}\nabla f(\theta_{t-1})\]
\[\text{Secant condition:} B_{t}(\theta_{t} - \theta_{t-1}) = \nabla f(\theta_{t}) - \nabla f(\theta_{t-1})\]

This is the key idea behind BFGS and its limited-memory forms: mimic curvature using gradient differences, not explicit Hessians.

Distinctions and Comparisons

  • Heavy Ball vs NAG. Both use momentum; NAG evaluates the gradient at the look-ahead point and is the one with the clean acceleration theory emphasized in the lecture.
  • SAG vs SVRG. SAG stores many gradients and is memory-heavy; SVRG stores little but pays an extra gradient-evaluation cost and has an extra loop-length hyperparameter.
  • Second-order vs quasi-Newton. Newton is genuinely second-order because it uses the Hessian. Quasi-Newton is formally first-order because curvature is only approximated from gradient history.
  • Acceleration vs variance reduction. Acceleration combats bad conditioning; variance reduction combats stochastic noise in finite sums. They solve different bottlenecks.

Exam-Oriented Understanding

  • When asked about Nesterov, say why it is accelerated: the rate improves from 1/t to 1/t2 in the smooth convex case.
  • When asked about variance reduction, the core phrase is "reuse past gradient information to reduce variance while keeping stochastic-style updates".
  • For SAG versus SVRG, the safest contrast is memory cost versus per-step computation cost.
  • For Newton, always write the inverse Hessian update and mention the one-step convergence on quadratics.
  • Do not call quasi-Newton second-order in the strict sense used in the lecture summary slide.

Source References

  • Optimization Lecture 2 (APM52445-Optimization-Lect2.pdf), slides 36-46: Momentum, Heavy Ball, Nesterov acceleration, accelerated rates and interpretation.
  • Optimization Lecture 2 (APM52445-Optimization-Lect2.pdf), slides 47-58: Variance reduction motivation, SAG, SVRG, theoretical comparison and hyperparameters.
  • Optimization Lecture 2 (APM52445-Optimization-Lect2.pdf), slides 59-70: Newton method, local quadratic model, quadratics, quasi-Newton and BFGS summary.
  • Optimization Lecture 3 (APM52445-Optimization-Lect3.pdf), slides 10-46: Recap and complementary insight on acceleration, second-order methods, and variance reduction.
Only lecture PDFs are used as content sources here. The sample exam is used only to choose emphasis and exam-answer style.

Relevant Exam Alignment

The sample exam asks for the intuition behind Nesterov acceleration, for a variance-reduced method and its idea, for the specific SAG versus SVRG tradeoff, and for Newton's update together with its behavior on quadratic objectives.

This chapter therefore needs both equations and short qualitative summaries: what information is reused, what cost is added, and what bottleneck is being fixed.

← DL Foundations Back to Index DL Training and Regularization →