A digression into optimization, needed to explain how each iteration refines its approximate solution (43:35, 44:23).

The setting

  • Goal: iteratively compute x* = argmin_{x ∈ ℝⁿ} f(x) for f : ℝⁿ → ℝ (44:43).
  • First-order method assumptions:
    1. An oracle that, given x ∈ ℝⁿ, returns f(x) and ∇f(x) (45:58).
    2. A bound on the Hessian's behaviour — the update rule may only use the oracle's output, but the analysis may use the Hessian bound (46:56, 57:03, 57:26).
  • Hessian at x: the n × n matrix with (∇²f(x))_{ij} = ∂²f(x)/∂xᵢ∂xⱼ (46:56).

The Hessian condition

  • Assume constants 0 < μ < L with μ·I ⪯ ∇²f(x) ⪯ L·I for all x ∈ ℝⁿ (48:38, 49:13).
  • Loewner ordering: A ⪯ B means B − A is positive semidefinite, equivalently xᵀ(B − A)x ≥ 0 for all x (49:13, 49:56, 50:56).
  • Interpretation: the Hessian's largest eigenvalue is at most L, its smallest is at least μ — the matrix is well-conditioned, with no eigenvalue too large or too close to zero (50:30).
  • Justification sketched via the Rayleigh quotient: the largest eigenvalue is max_{‖x‖=1} xᵀAx, i.e. xᵀAx / xᵀx in general; comparing against xᵀ(L·I)x = L‖x‖² gives the eigenvalue bound. Taken on faith for this course (51:37, 52:07, 52:29, 52:50).

Orders of methods

  • k-th order method = the update rule has access to k-th order partial derivatives; using the Hessian in the update rule makes a method second order (57:26).
  • Interior point will use a second-order method (Newton's) and will not assume control over third-order partials — a different kind of control is used instead (57:44, 58:02).
  • Newton's method is not a pure first-order method here: its update rule genuinely needs the Hessian (58:24).

What an iterative method is

  • Start at x₀ ∈ ℝⁿ, compute x_{k+1} from x_k via an update rule, stop after some number of iterations (53:36).
  • Target guarantee: f(x_{k+1}) − f(x*) ≤ α·( f(x_k) − f(x*) ) with α small (55:08, 56:38).
  • By induction the error after k steps is multiplied by αᵏ, so α < 1 means exponentially decaying error (56:38, 57:03).