Second-Order Optimization Methods

Second-order optimization methods use curvature information (the Hessian matrix or its surrogates) in addition to the gradient to determine search directions, achieving quadratic local convergence near minima. They apply wherever smooth objectives must be minimized — machine learning, control, statistics, computational physics — especially when ill-conditioning cripples first-order methods. Pioneered by Newton, formalized in the 19th–20th centuries, and now central to large-scale numerical optimization.

Second-order optimization methods minimize a sufficiently smooth function $f : R^{n} \to R$ by exploiting its local quadratic model $f (x) + \nabla f (x)^{⊤} p + \frac{1}{2} p^{⊤} \nabla^{2} f (x) p$ , solving for the step $p$ that minimizes this model. Whereas gradient descent uses only first derivatives and converges linearly with a rate governed by the condition number, Newton-type methods incorporate the Hessian to rescale the geometry, yielding affine-invariant iterations and quadratic convergence in a neighborhood of a nondegenerate minimizer. They matter because conditioning is the dominant obstacle in practice: ill-conditioned problems that take millions of gradient steps may need a handful of Newton steps. The surprising fact is that despite the apparent $O (n^{3})$ cost of solving the Newton system, modern quasi-Newton and matrix-free Hessian-vector techniques deliver near-second-order behavior at near-first-order cost, making these methods competitive even at the scale of billion-parameter models.

The Core Insight

A gradient tells you which way is downhill; curvature tells you how far to go. By modeling $f$ locally as a quadratic and jumping to that quadratic's minimizer, Newton's method automatically adapts the step length to the local geometry — taking long steps in flat directions and short steps in steep ones. This makes the iteration invariant under affine changes of coordinates, eliminating the dependence on conditioning that plagues first-order methods.

Formal Statement

Newton's Method for Optimization

Let $f \in C^{2} (R^{n})$ with gradient $g (x) = \nabla f (x)$ and Hessian $H (x) = \nabla^{2} f (x)$ . The Newton iteration is

x_{k + 1} = x_{k} - H (x_{k})^{- 1} g (x_{k}) .

⟳Set the gradient of the second-order Taylor model

m_{k} (p) = f (x_{k}) + g (x_{k})^{⊤} p + \frac{1}{2} p^{⊤} H (x_{k}) p

to zero, giving

H (x_{k}) p = - g (x_{k})

Here $x_{k} \in R^{n}$ is the current iterate, $g (x_{k}) \in R^{n}$ the gradient, and $H (x_{k}) \in R^{n \times n}$ the symmetric Hessian. The Newton direction $p_{k}$ solves the linear system $H (x_{k}) p_{k} = - g (x_{k})$ .

Quadratic Model and Step

The local quadratic model at $x_{k}$ is

m_{k} (p) = f (x_{k}) + g (x_{k})^{⊤} p + \frac{1}{2} p^{⊤} H (x_{k}) p .

⟳This is the truncated Taylor expansion of

f (x_{k} + p)

to second order; the remainder is

o (∥ p ∥^{2})

C^{2}

smoothness.

When $H (x_{k}) ≻ 0$ , $m_{k}$ is strictly convex and its unique minimizer is $p_{k} = - H (x_{k})^{- 1} g (x_{k})$ , the Newton step.

Local Quadratic Convergence of Newton's Method

Suppose $f \in C^{2}$ near a point $x^{⋆}$ with $g (x^{⋆}) = 0$ , $H (x^{⋆}) ≻ 0$ , and $H$ Lipschitz with constant $L$ in a neighborhood of $x^{⋆}$ . Then there exists $δ > 0$ such that for $∥ x_{0} - x^{⋆} ∥ < δ$ the Newton iterates satisfy

∥ x_{k + 1} - x^{⋆} ∥ \leq \frac{L}{2 σ _{m i n}} ∥ x_{k} - x^{⋆} ∥^{2},

where $σ_{m i n} = λ_{m i n} (H (x^{⋆})) /2$ . The convergence is quadratic: the number of correct digits roughly doubles each step.

We establish [3] in numbered steps.

Step 1 — Error in terms of gradient. Since

g (x^{⋆}) = 0

, by the fundamental theorem of calculus

g (x_{k}) = g (x_{k}) - g (x^{⋆}) = (\int_{0}^{1} H (x^{⋆} + t (x_{k} - x^{⋆})) d t) (x_{k} - x^{⋆}) .

⟳Apply

g (b) - g (a) = \int_{0}^{1} H (a + t (b - a)) (b - a) d t

to the vector-valued map

g

Step 2 — Express the new error. Write

e_{k} = x_{k} - x^{⋆}

. From [1],

e_{k + 1} = e_{k} - H (x_{k})^{- 1} g (x_{k}) = H (x_{k})^{- 1} (H (x_{k}) e_{k} - g (x_{k})) .

⟳Multiply

e_{k}

H (x_{k})^{- 1} H (x_{k})

and subtract the Newton step term.

Step 3 — Bound the residual. Using [4],

H (x_{k}) e_{k} - g (x_{k}) = \int_{0}^{1} (H (x_{k}) - H (x^{⋆} + t e_{k})) e_{k} d t .

⟳Substitute the integral form of

g (x_{k})

and pull

e_{k}

out.

By Lipschitz continuity, $∥ H (x_{k}) - H (x^{⋆} + t e_{k}) ∥ \leq L ∥ x_{k} - (x^{⋆} + t e_{k}) ∥ = L (1 - t) ∥ e_{k} ∥$ , so the integral norm is bounded by $L ∥ e_{k} ∥^{2} \int_{0}^{1} (1 - t) d t = \frac{L}{2} ∥ e_{k} ∥^{2}$ .

Step 4 — Combine. For

x_{k}

close enough that

∥ H (x_{k})^{- 1} ∥ \leq 1/ σ_{m i n}

(continuity of eigenvalues), [5] and the Step-3 bound give

∥ e_{k + 1} ∥ \leq \frac{1}{σ _{m i n}} \cdot \frac{L}{2} ∥ e_{k} ∥^{2},

which is [3]. Choosing

δ

so that

\frac{L}{2 σ _{m i n}} δ < 1

guarantees the iterates remain in the neighborhood and converge.

■

⟳The contraction factor

\frac{L}{2 σ _{m i n}} ∥ e_{k} ∥ < 1

ensures

∥ e_{k + 1} ∥ < ∥ e_{k} ∥

Isaac Newton | 1643–1727

Newton introduced the root-finding iteration that bears his name (the method of fluxions, c. 1669, circulated 1671) for solving polynomial equations, applying successive linear corrections. Joseph Raphson simplified it in 1690 into the recursive form we recognize today — hence "Newton–Raphson." Though Newton conceived it for univariate root-finding, the optimization version (applying the method to $\nabla f = 0$ ) is the direct multivariate generalization, with the Hessian replacing the scalar second derivative.

Building Intuition

Picture standing on a curved terrain in fog. Gradient descent feels only the local slope and shuffles downhill a fixed distance — too cautious in a long flat valley, too reckless on a steep cliff. Newton's method, by contrast, fits a paraboloid to the terrain at your feet and walks straight to that paraboloid's bottom. In a perfectly quadratic bowl, one Newton step lands exactly at the minimum regardless of how stretched or rotated the bowl is.

The deep reason is affine invariance: if you reparametrize $x = A \tilde{x}$ for invertible $A$ , Newton's iterates transform consistently, so the method "doesn't see" the conditioning. Gradient descent, tied to the Euclidean metric, sees everything through the lens of the worst direction. The Hessian effectively supplies a local metric — Newton's method is steepest descent in the geometry $⟨ u, v ⟩_{H} = u^{⊤} H v$ .

Newton step vs. gradient step in an ill-conditioned quadratic bowl

Worked Examples

Newton on a 2D Quadratic

Given:

f (x) = \frac{1}{2} x^{⊤} A x - b^{⊤} x

with

A = (4113)

b = (12)

, starting at

x_{0} = (0, 0)^{⊤}

. Step 1. Gradient:

g (x) = A x - b

. At

x_{0}

g_{0} = - b = (- 1, - 2)^{⊤}

. Step 2. Hessian:

H = A

(constant). Compute

A^{- 1}

det A = 12 - 1 = 11

, so

A^{- 1} = \frac{1}{11} (3 - 1 - 1 4)

. Step 3. Newton step:

p_{0} = - A^{- 1} g_{0} = A^{- 1} b = \frac{1}{11} (3 - 1 - 1 4) (12) = \frac{1}{11} (17)

. Step 4.

x_{1} = x_{0} + p_{0} = (1/11, 7/11)^{⊤}

. Verify:

g (x_{1}) = A x_{1} - b = b - b = 0

x_{1} = (0.0909, 0.6364)^{⊤} — exact minimizer in ONE step (dimensionless)

For a quadratic, Newton's method converges in a single iteration.

Newton on a Nonquadratic Scalar

Given: minimize

f (x) = x^{4} - 3 x^{2} + x

, start

x_{0} = 2

. Step 1.

f^{'} (x) = 4 x^{3} - 6 x + 1

f^{''} (x) = 12 x^{2} - 6

. Step 2. At

x_{0} = 2

f^{'} = 32 - 12 + 1 = 21

f^{''} = 48 - 6 = 42

x_{1} = 2 - 21/42 = 1.5

. Step 3. At

x_{1} = 1.5

f^{'} = 13.5 - 9 + 1 = 5.5

f^{''} = 27 - 6 = 21

x_{2} = 1.5 - 5.5/21 = 1.2381

. Step 4. At

x_{2} = 1.2381

f^{'} = 7.594 - 7.429 + 1 = 1.166

f^{''} = 18.40 - 6 = 12.40

x_{3} = 1.2381 - 0.0940 = 1.1441

. Step 5. At

x_{3}

f^{'} \approx 5.992 - 6.864 + 1 = 0.128

x_{4} \approx 1.1441 - 0.0108 = 1.1333

The local minimizer is $x^{⋆} \approx 1.1318$ (root of $4 x^{3} - 6 x + 1$ ).

x^{⋆} \approx 1.1318 — note the doubling of accuracy per step (dimensionless)

Errors: $0.87 \to 0.37 \to 0.106 \to 0.0123 \to 0.00015$ — clear quadratic convergence near the end.

Common Misconceptions

Newton's method does NOT globally converge, nor does it always minimize. The pure iteration [1] finds stationary points (

g = 0

): minima, maxima, or saddle points indiscriminately. If

H (x_{k})

is indefinite, the "Newton step" may point uphill or toward a saddle. Far from a solution, the full step can overshoot or diverge. Practical implementations require globalization: a line search (Wolfe conditions) or trust region, plus Hessian modification (e.g., adding

τ I

to enforce positive definiteness) so the step is a descent direction.

Consider $f (x) = - \frac{1}{2} x^{2}$ in 1D, with maximizer at $0$ . Newton's method gives $x_{k + 1} = x_{k} - (- x_{k}) / (- 1) = x_{k} - x_{k} = 0$ — it lands on the maximum in one step, which is the wrong target for minimization. More dramatically, for $f (x) = x^{2} + 1$ , Newton's iteration $x_{k + 1} = - x_{k}^{3}$ diverges for any $∣ x_{0} ∣ > 1$ despite $f$ being smooth and convex with a unique minimum at $0$ . Curvature-blind faith in [1] without safeguards fails.

Connections

Second-order methods sit at a crossroads of numerical linear algebra and optimization. The Newton step requires solving $H p = - g$ , linking to Conjugate Gradient Method (truncated/inexact Newton solves this iteratively, needing only Hessian-vector products). The dual viewpoint of building curvature from gradient differences yields Quasi-Newton Methods (BFGS, DFP, L-BFGS). When $H$ is the Fisher information, Newton becomes Natural Gradient Descent, central to information geometry. Constrained problems route through Sequential Quadratic Programming and Interior Point Methods, both Newton at their core. The affine-invariance theme connects to Self-Concordant Functions, Nesterov–Nemirovski's framework giving Newton global complexity bounds. Contrast with Gradient Descent clarifies the curvature trade-off.

Real-World Applications

Logistic regression & GLMs (IRLS): Iteratively Reweighted Least Squares is exactly Newton's method on the log-likelihood; statistical software (R's glm, statsmodels) uses it by default.
Interior-point LP/SDP solvers: CVXOPT, MOSEK, Gurobi's barrier method take damped Newton steps on self-concordant barrier functions, solving million-variable convex programs.
Deep learning second-order optimizers: K-FAC (Kronecker-Factored Approximate Curvature) and Shampoo approximate the Fisher/Hessian to train large neural networks faster per step than Adam.
Bundle adjustment in computer vision: Levenberg–Marquardt (a damped Gauss–Newton) reconstructs 3D scenes from thousands of images in COLMAP and photogrammetry pipelines.
Power-flow analysis: Newton–Raphson solves the nonlinear AC power-flow equations in electrical grid simulation (PowerWorld, MATPOWER).
Molecular geometry optimization: Quantum chemistry packages (Gaussian, ORCA) use quasi-Newton (BFGS) to find equilibrium molecular structures on potential-energy surfaces.
Maximum-likelihood estimation: Econometrics and biostatistics fit nonlinear models via Newton/Fisher scoring, reporting the inverse Hessian as the asymptotic covariance.

Historical Development

1669: Newton describes his iterative method for polynomial roots in De analysi, circulated in manuscript.
1690: Joseph Raphson publishes the simplified recursive form, giving "Newton–Raphson."
1740: Thomas Simpson extends the method to general (non-polynomial) equations and to systems via derivatives.
1847: Augustin-Louis Cauchy introduces the gradient (steepest descent) method, the first-order foil to Newton.
1944: Kenneth Levenberg proposes damping the Gauss–Newton step; Donald Marquardt refines it in 1963 — the LM algorithm.
1959–1963: William Davidon (1959) invents variable-metric (quasi-Newton) methods; Fletcher & Powell (1963) develop DFP.
1970: Broyden, Fletcher, Goldfarb, and Shanno independently derive the BFGS update, the most successful quasi-Newton formula.
1980s: Trust-region theory (Moré, Sorensen) and inexact/truncated Newton (Dembo, Eisenstat, Steihaug) mature; Nocedal's L-BFGS (1980) enables large-scale use.
1994: Nesterov & Nemirovski's Interior-Point Polynomial Algorithms establishes self-concordance, giving Newton's method polynomial global complexity for convex problems.

Subtleties & Limits

The fundamental tension is cost versus curvature. Forming and factorizing $H$ costs $O (n^{2})$ storage and $O (n^{3})$ time — prohibitive for $n \sim 1 0^{9}$ . Matrix-free Hessian-vector products (via automatic differentiation, $O (n)$ each) plus Krylov solvers help, but how to robustly exploit curvature in stochastic, non-convex deep learning remains open: sampled Hessians are noisy, indefinite, and rapidly changing. Saddle-point escape (where Newton is attracted rather than repelled) motivates saddle-free Newton and cubic-regularized Newton (Nesterov–Polyak, 2006), which achieves $O (ϵ^{- 3/2})$ complexity to second-order stationary points — but its subproblem is itself nontrivial. Whether a practical, provably efficient stochastic second-order method can beat well-tuned first-order methods at scale is an active research frontier; the theoretical advantage (affine invariance, fast local rate) has not yet decisively translated into universal practical dominance for non-convex problems.