04. Numerical Analysis for Optimization — Making Paper Methods Work in Code

// BACKGROUND 4/6 — approximation error, floating-point arithmetic, iterative method, convergence, condition number

An optimization algorithm can be mathematically correct yet unstable on a computer. Numerical analysis studies that gap.

Approximation error

Approximation replaces an exact value with an easier one. Taylor expansions, finite differences, and surrogate models are all approximations.

Approximation error is usually understood as

$$\text{error}=\text{true value}-\text{approximation}.$$

Knowing the rate at which the error shrinks helps determine how to choose the step size or mesh size.

Floating-point arithmetic

A computer stores real numbers with finitely many bits. Real-number operations are therefore rounded operations rather than exact real arithmetic.

Problems arise when a small difference is produced by subtracting two large numbers:

$$f(x+h)-f(x).$$

If $h$ is too small, the two numbers are almost identical and significant digits disappear. This is why numerical differentiation is less stable than automatic differentiation.

Iterative methods

Many optimization algorithms do not find the answer in one operation. Instead, they create a sequence:

$$x_0,x_1,x_2,\dots$$

Each iteration moves to a better candidate, and the process stops when the candidate is judged good enough. Gradient descent, Newton's method, and conjugate gradient are all iterative methods.

Convergence

Convergence is the property that an iterative sequence approaches some target.

Perspective on convergence	Question
Function value	Does $f(x_k)$ approach the minimum value?
Variable	Does $x_k$ approach the solution $x^\ast$?
Gradient norm	Does $\|\nabla f(x_k)\|$ approach 0?

When comparing algorithms, both "how cheap is one iteration?" and "how many iterations are required?" must be considered.

Condition number

The condition number indicates how much error in the input is amplified into error in the output. For a linear system $Ax=b$, a large condition number means even a small error can greatly perturb the solution.

$$\kappa(A)=\|A\|\|A^{-1}\|.$$

A large Hessian condition number produces a long, narrow valley. Gradient descent zigzags and moves slowly on such a problem. Preconditioning attempts to make this valley rounder.

Implementation checklist

• Do values jump to NaN or Inf?
• Is the gradient norm decreasing?
• Did the process stop because the step size became too small?
• Does the problem have an excessively large condition number?
• Is the stopping criterion appropriate for the problem's scale?

Next: Probability and Statistics Background