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).

Test Your Knowledge: Practice Questions for "Newton's Method"

Single choice pitfall questions with instant feedback and mistake tracking.