Second-Order Optimization Methods

⚡ Key Takeaways

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.

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

DefinitionNewton's Method for Optimization

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

1

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

Derivation hint: Set the gradient of the second-order Taylor model $m_k(p)=f(x_k)+g(x_k)^\top p+\tfrac12 p^\top H(x_k)p$ to zero, giving $H(x_k)p=-g(x_k)$ . Here $x_k\in\mathbb{R}^n$ is the current iterate, $g(x_k)\in\mathbb{R}^n$ the gradient, and $H(x_k)\in\mathbb{R}^{n\times n}$ the symmetric Hessian. The Newton direction $p_k$ solves the linear system $H(x_k)p_k = -g(x_k)$ .

DefinitionQuadratic Model and Step

The local quadratic model at $x_k$ is

2

\quad m_k(p)=f(x_k)+g(x_k)^\top p+\tfrac12\,p^\top H(x_k)\,p.

Derivation hint: This is the truncated Taylor expansion of $f(x_k+p)$ to second order; the remainder is $o(\|p\|^2)$ by $C^2$ smoothness. When $H(x_k)\succ 0$ , $m_k$ is strictly convex and its unique minimizer is $p_k=-H(x_k)^{-1}g(x_k)$ , the Newton step.

TheoremLocal Quadratic Convergence of Newton's Method

Suppose $f\in C^2$ near a point $x^\star$ with $g(x^\star)=0$ , $H(x^\star)\succ 0$ , and $H$ Lipschitz with constant $L$ in a neighborhood of $x^\star$ . Then there exists $\delta>0$ such that for $\|x_0-x^\star\|<\delta$ the Newton iterates satisfy

3

\quad \|x_{k+1}-x^\star\| \le \frac{L}{2\,\sigma_{\min}}\,\|x_k-x^\star\|^2,

where $\sigma_{\min}=\lambda_{\min}(H(x^\star))/2$ . The convergence is quadratic: the number of correct digits roughly doubles each step.

Proof

We establish [3] in numbered steps.

Step 1 — Error in terms of gradient. Since $g(x^\star)=0$ , by the fundamental theorem of calculus

4

\quad g(x_k)=g(x_k)-g(x^\star)=\Big(\int_0^1 H\big(x^\star+t(x_k-x^\star)\big)\,dt\Big)(x_k-x^\star).

Derivation hint: Apply $g(b)-g(a)=\int_0^1 H(a+t(b-a))(b-a)\,dt$ to the vector-valued map $g$ .

Step 2 — Express the new error. Write $e_k=x_k-x^\star$ . From [1],

5

\quad e_{k+1}=e_k-H(x_k)^{-1}g(x_k)=H(x_k)^{-1}\big(H(x_k)e_k-g(x_k)\big).

Derivation hint: Multiply $e_k$ by $H(x_k)^{-1}H(x_k)$ and subtract the Newton step term.

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

6

\quad H(x_k)e_k-g(x_k)=\int_0^1\big(H(x_k)-H(x^\star+te_k)\big)e_k\,dt.

Derivation hint: Substitute the integral form of $g(x_k)$ and pull $e_k$ out. By Lipschitz continuity, $\|H(x_k)-H(x^\star+te_k)\|\le L\,\|x_k-(x^\star+te_k)\|=L(1-t)\|e_k\|$ , so the integral norm is bounded by $L\|e_k\|^2\int_0^1(1-t)\,dt=\tfrac{L}{2}\|e_k\|^2$ .

Step 4 — Combine. For $x_k$ close enough that $\|H(x_k)^{-1}\|\le 1/\sigma_{\min}$ (continuity of eigenvalues), [5] and the Step-3 bound give

7

\quad \|e_{k+1}\|\le \frac{1}{\sigma_{\min}}\cdot\frac{L}{2}\|e_k\|^2,

which is [3]. Choosing $\delta$ so that $\frac{L}{2\sigma_{\min}}\delta<1$ guarantees the iterates remain in the neighborhood and converge. $\blacksquare$ Derivation hint: The contraction factor $\frac{L}{2\sigma_{\min}}\|e_k\|<1$ ensures $\|e_{k+1}\|<\|e_k\|$ .

∎

IN

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.

🧠 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 $\langle u,v\rangle_H = u^\top H v$ .

Figure

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

ExampleNewton on a 2D Quadratic

Given: $f(x)=\tfrac12 x^\top A x - b^\top x$ with $A=\begin{pmatrix}4&1\\1&3\end{pmatrix}$ , $b=\begin{pmatrix}1\\2\end{pmatrix}$ , starting at $x_0=(0,0)^\top$ .

Step 1. Gradient: $g(x)=Ax-b$ . At $x_0$ : $g_0=-b=(-1,-2)^\top$ .

Step 2. Hessian: $H=A$ (constant). Compute $A^{-1}$ : $\det A = 12-1=11$ , so $A^{-1}=\tfrac1{11}\begin{pmatrix}3&-1\\-1&4\end{pmatrix}$ .

Step 3. Newton step: $p_0=-A^{-1}g_0=A^{-1}b=\tfrac1{11}\begin{pmatrix}3&-1\\-1&4\end{pmatrix}\begin{pmatrix}1\\2\end{pmatrix}=\tfrac1{11}\begin{pmatrix}1\\7\end{pmatrix}$ .

Step 4. $x_1=x_0+p_0=(1/11,\,7/11)^\top$ . Verify: $g(x_1)=Ax_1-b=b-b=0$ .

\boxed{x_1=(0.0909,\,0.6364)^\top \text{ — exact minimizer in ONE step (dimensionless)}}

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

ExampleNewton on a Nonquadratic Scalar

Given: minimize $f(x)=x^4 - 3x^2 + x$ , start $x_0=2$ .

Step 1. $f'(x)=4x^3-6x+1$ , $f''(x)=12x^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^\star\approx 1.1318$ (root of $4x^3-6x+1$ ).

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

Errors: $0.87\to0.37\to0.106\to0.0123\to0.00015$ — clear quadratic convergence near the end.

⚠️ Common mistake

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 $\tau I$ to enforce positive definiteness) so the step is a descent direction.

Counterexample

Consider $f(x)=-\tfrac12 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)=\sqrt{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.

connection

Second-order methods sit at a crossroads of numerical linear algebra and optimization. The Newton step requires solving $Hp=-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.

🔬 Where this appears

⏳ History

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

open-problem

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 10^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(\epsilon^{-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.

Formal Statement

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also