The update rule

  • From the current iterate x₀ ∈ ℝⁿ, the next iterate is 4:10:

    x₁ = x₀ − (∇²f(x₀))⁻¹ ∇f(x₀)

  • This is the exact rule that gets analyzed for the rest of the lecture 5:01.

Derivation: minimize the second-order Taylor model

  • Gradient descent minimizes the first-order Taylor approximation plus the error term from Taylor's theorem 5:01, 5:26.

  • Newton's method instead minimizes the second-order Taylor expansion 5:26:

    f(y) ≈ f(x₀) + ⟨∇f(x₀), y − x₀⟩ + ½⟨y − x₀, ∇²f · (y − x₀)⟩ 5:48

  • Newton's method pretends this approximation is an equality and minimizes the right-hand side; doing the calculus gives exactly x₁ = x₀ − (∇²f)⁻¹∇f 6:32.

MethodOracle accessModel minimizedStep
Gradient descentf, ∇f1st-order Taylor + error boundstep along −∇f 5:01
Newton's methodf, ∇f, ∇²f2nd-order Taylor, treated as exact−(∇²f)⁻¹∇f 4:10, 6:32
  • The remaining task is purely quantitative: how well does this step do? 6:58