Newton's Method

Newton's method uses second-order information: take the second-order Taylor expansion at $w$, $f(w + \Delta w) \approx f(w) + \nabla f^T\Delta w + \frac{1}{2}\Delta w^T H\Delta w$ (H = Hessian), differentiate w.r.t. $\Delta w$ and set to zero: $\nabla f + H\Delta w = 0$, giving the Newton step $\Delta w = -H^{-1}\nabla f$. Geometrically it fits a quadratic surface and jumps straight to its vertex: exactly one step for quadratics, and local quadratic convergence for smooth functions — the error decays quadratically, $\Vert w_{k+1} - w^*\Vert \le C\Vert w_k - w^*\Vert^2$, doubling correct digits per iteration ($10^{-3} \to 10^{-6} \to 10^{-12}$), versus linear convergence $(1 - 1/\kappa)^t$ for gradient descent.

a canonical interview comparison with GD. Ill-conditioned example: $f(x,y) = x^2 + 100y^2$. Hessian $H = \mathrm{diag}(2, 200)$, condition number $\kappa = 200/2 = 100$. GD zig-zags along the steep $y$ direction and needs $O(\kappa)$ iterations; Newton computes $H^{-1}\nabla f = (x, y)^T$, effectively a coordinate transform that removes the scale difference, and reaches the origin in one step.

first-order rates are dominated by the condition number, while Newton's $H^{-1}$ isotropizes the space and converges in one step on ill-conditioned problems; the cost is $O(D^3)$ per step to solve the linear system and $O(D^2)$ memory for the Hessian, infeasible for high-dimensional deep networks — hence approximations: L-BFGS ($O(D)$ memory, inverse-Hessian built from gradient history) and Gauss-Newton ($H \approx J^TJ$ for least squares, made invertible via $J^TJ + \lambda I$). For non-convex functions H can be indefinite and the Newton direction is not a descent direction; fixes include damped Newton and regularization $H + \lambda I$ (Levenberg-Marquardt).

Derive the Newton step $\Delta w = -H^{-1}\nabla f$ from the second-order Taylor expansion (show the full stationarity derivation).

Why does Newton converge in one step on quadratics and quadratically in general? Explain the rate $\Vert w_{k+1}-w^*\Vert \le C\Vert w_k-w^*\Vert^2$.

Ill-conditioned example $f = x^2 + 100y^2$: estimate steps for GD ($\kappa=100$) vs Newton and explain why Newton lands in one step.

What is Newton's cost ($O(D^3)$ per step, $O(D^2)$ memory)? How do L-BFGS and Gauss-Newton approximate the Hessian?

For non-convex functions the Hessian can be indefinite — why does the Newton direction become unreliable? How do damped Newton and $H + \lambda I$ (Levenberg-Marquardt) fix it?