Second-Order Optimization & Newton's Method
“Newton step Delta x = - H^{-1} grad(f), quadratic convergence, scale invariance, and Hessian inversion cost.”
1.Second-Order Optimization & The Quadratic Model
§ 5.1.While Gradient Descent approximates the loss surface with a flat tangent plane, Newton's Method fits a quadratic paraboloid using the Hessian matrix:
f(x + Delta x) ≈ f(x) + grad(f(x))^T Delta x + (1/2) Delta x^T H(x) Delta x.
Derivation of the Newton Step:
Differentiating the quadratic surrogate with respect to Delta x and setting to zero:
grad(f(x)) + H(x) Delta x = 0 => Delta x = - [H(x)]^{-1} grad(f(x)).
x_{k+1} = x_k - [H(x_k)]^{-1} grad(f(x_k)).
Comparison: First-Order vs Second-Order Optimization:
- Gradient Descent: Per-step cost O(d), linear convergence O(c^k), highly sensitive to feature scaling and conditioning.
- Newton's Method: Per-step cost O(d^3), quadratic convergence O(e_k^2), completely affine-invariant, but fails if Hessian is singular or indefinite.
2. Worked Practice Problem: Exact Single-Step Newton Convergence
Invert the 2x2 Hessian matrix accurately using the adjugate formula H^{-1} = (1 / det(H)) * adj(H).
Problem: Apply one iteration of Newton's method to minimize f(x, y) = 2x^2 + y^2 - 2xy - 4x starting from initial guess (x0, y0) = (0, 0). Show that the step jumps directly to the exact global minimum.
Step 1: Compute gradient vector grad(f):
df/dx = 4x - 2y - 4
df/dy = 2y - 2x
At (x0, y0) = (0, 0): grad(f)(0, 0) = [ -4, 0 ]^T.
Step 2: Compute Hessian matrix H:
d^2 f / dx^2 = 4
d^2 f / dy^2 = 2
d^2 f / dxdy = -2
H = [ [ 4, -2], [-2, 2] ].
Step 3: Compute Hessian inverse H^{-1}:
det(H) = (4)(2) - (-2)(-2) = 8 - 4 = 4 > 0 (Positive Definite).
H^{-1} = (1 / 4) * [ [2, 2], [2, 4] ] = [ [1/2, 1/2], [1/2, 1] ].
Step 4: Compute Newton step Delta x = - H^{-1} * grad(f):
Delta x = - [ [1/2, 1/2], [1/2, 1] ] * [ -4, 0 ]^T
Delta x = - [ (1/2)(-4) + 0, (1/2)(-4) + 0 ]^T = - [ -2, -2 ]^T = [ 2, 2 ]^T.
Step 5: Compute updated point x1 = x0 + Delta x:
[ x1, y1 ]^T = [ 0, 0 ]^T + [ 2, 2 ]^T = [ 2, 2 ]^T.
Step 6: Verify that (2, 2) is the exact critical point:
df/dx(2, 2) = 4(2) - 2(2) - 4 = 8 - 4 - 4 = 0.
df/dy(2, 2) = 2(2) - 2(2) = 4 - 4 = 0.
grad(f)(2, 2) = [ 0, 0 ]^T.
Conclusion: In exactly ONE iteration, Newton's method jumps from (0, 0) directly to the exact global minimum (2, 2).
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.