The Local Optimisation Problem

Summary

Local optimisation seeks a local minimiser $x_{\ast }$ of a (generally non-convex, twice-differentiable) objective $f:{\mathbb{R}}^N\to \mathbb{R}$ via an iterative loop that alternates a search-direction decision and a step-size (line-search) decision. In modern machine learning the objective is an empirical risk evaluated on sub-sampled mini-batches, so gradients and values arrive corrupted by a genuine Gaussian likelihood rather than to machine precision. This noise — of magnitude far beyond machine epsilon — breaks classical notions of stability and step-size selection, and is exactly the opening for the probabilistic viewpoint.

Overview

Chapters II (integration) and III (linear algebra) reconstructed linear numerical tasks as inference. Local optimisation is the first nonlinear task (§25). The recurring PN thesis applies: optimisation algorithms are probabilistic agents whose step-size and direction choices are expected-loss-minimising actions. But unlike earlier chapters, Part IV moves away from merely re-deriving classical methods and instead develops new functionality for the noisy, big-data regime that classical solvers handle poorly (Ch. 24).

The key numerical challenge separating machine learning from classical numerics is the central role of big external data. When datasets are large, data points are sub-sampled (“batched”) for every internal computation. Batching introduces stochasticity — noise of a magnitude far beyond machine precision — and classical notions of stability no longer apply. It no longer makes sense to speak of a “correct number computed with a tiny error”; a real likelihood function must enter the picture. If this likelihood is not modelled, a number of visible problems arise (e.g. the disappointing algorithmic landscape of deep learning).

Main Content

Problem setting

Unconstrained local minimisation

Given $f:{\mathbb{R}}^N\to \mathbb{R}$, at least twice continuously differentiable, with gradient and Hessian

$$\nabla f:{\mathbb{R}}^N\to {\mathbb{R}}^N,[\nabla f(x){]}_i=\frac{\partial f(x)}{\partial x_i},B:{\mathbb{R}}^N\to {\mathbb{R}}^{N\times N},[B(x){]}_{ij}=\frac{{\partial }^{2}f(x)}{\partial x_i\partial x_j},$$

a local minimiser is

$$x_{\ast }=\arg \underset{x}{\min }f(x):\iff (\nabla f(x_{\ast })=0)\wedge (B(x_{\ast })\text{is spd}).$$

$f$ is strongly convex if $B(x)$ is (strictly) positive definite everywhere; this is not generally assumed. $N$ ranges from a handful (control) to billions (deep learning). The setting is unconstrained and seeks a local (not global — cf. The Global Optimisation Problem) minimum.

The generic iterative loop

Classical unconstrained solvers (Algorithm 25.1) mirror the linear solvers of Ch. III: from $x_i$ they produce $x_{i+1}$ by two principal steps.

Direction–then–step-length iteration

1. Search direction $d_i\in {\mathbb{R}}^N$: choose $d_i$ using calls to the black boxes $f$ and/or $\nabla f$. The naïve choice is steepest / gradient descent, $d_i=-\nabla f(x_i)$.
2. Step size ${\alpha }_i\in {\mathbb{R}}_{+}$: the next iterate is $x_{i+1}=x_i+{\alpha }_i{d}_i$. Finding a good ${\alpha }_i$ is a univariate optimisation solved by a line search. A line search returning the exact univariate optimum ${\alpha }_{\ast }=\arg {\min }_{\alpha }f(x_i+\alpha d_i)$ is called perfect (an analytical device; it does not exist in practice).

The line search operates on the projected univariate sub-problem $f(\alpha ):=f(x_i+\alpha d_i)$ with derivative the projected gradient $f^{\prime }(\alpha )=d_i^{\top }\nabla f(x_i+\alpha d_i)\in \mathbb{R}$.

Both $f(\alpha )$ and $f^{\prime }(\alpha )$ are scalars; a line search lives in an “inner loop” with almost no state propagation between calls (so the subscript $i$ is dropped). Typically only 1–10 evaluations are used. Performance depends crucially on both $d_i$ and ${\alpha }_i$ (Exercise 25.2): even gradient descent with a badly-chosen fixed step size fails.

Convergence of exact-line-search steepest descent (quadratic case)

For the strongly convex quadratic $f(x)=\frac{1}{2}{x}^{\top }Bx-b^{\top }x$ ($B$ spd, global min $x_{\ast }=B^{-1}b$) with eigenvalues $0<{\lambda }_1\le \cdots \le {\lambda }_N$, steepest descent with exact line searches, $x_{i+1}=x_i-\left(\frac{\nabla f_i^{\top }\nabla f_i}{\nabla f_i^{\top }B\nabla f_i}\right)\nabla f_i$, satisfies

$$\Vert x_{i+1}-x_{\ast }{\Vert }_B^2\le (\frac{{\lambda }_N-{\lambda }_1}{{\lambda }_N+{\lambda }_1}{)}^2\Vert x_i-x_{\ast }{\Vert }_B^2.$$

Interpretation. With condition number $\kappa (B)={\lambda }_N/{\lambda }_1$: an isometric problem ($\kappa =1$) converges in one step; large $\kappa$ makes the bound essentially vacuous (constant near 1), matching the known slowness of gradient descent. A general-function version (Thm. 25.3) shows $f(x_{i+1})-f(x_{\ast })\le c^2(f(x_i)-f(x_{\ast }))$ near a spd minimum, with $c\in (\frac{{\lambda }_N-{\lambda }_1}{{\lambda }_N+{\lambda }_1},1)$ — i.e. a linear convergence rate.

Convergence-rate vocabulary (S. Wright): sublinear ($r_i\to 0$ but $r_{i+1}/r_i\to 1$); linear/geometric ($r_{i+1}\le C{d}^i$, $0<d<1$); superlinear ($r_{i+1}/r_i\to 0$); quadratic ($r_{i+1}\le d{r}_i^2$, Newton’s rate — leading digits double each step).

Numerical uncertainty is a feature of data science (§26.1)

Classical numerics recovers methods as MAP/mean estimates under a Dirac likelihood $p(z\mid c,\mathcal{M})\propto \mathcal{N}(z;{\mu }_{\mathcal{M}},{\Sigma }_{\mathcal{M}})\delta (c-P_{\mathcal{M}}z)$: the Dirac encodes that a computer computes $c=Pz$ to machine precision (see Computation as Probabilistic Inference). Contemporary big-data tasks feature errors of a more drastic nature, requiring the Dirac to be replaced by an explicit likelihood.

Empirical risk minimisation and batch noise

Fitting parameters $x$ to data $\Xi =[{\xi }_1,\dots ,{\xi }_K]$ minimises a (regularised) empirical risk

$$\mathcal{L}(\Xi ,x)=r(x)+\frac{1}{K}\sum _{k=1}^K\ell ({\xi }_k,x),$$

with regulariser $r$ (data-independent) and per-datum loss $\ell$. For big data, one uses a random batch $\tilde{\Xi }=[{\xi }_{J_1},\dots ,{\xi }_{J_M}]$ of size $M\ll K$:

$$\tilde{\mathcal{L}}(x)=r(x)+\frac{1}{M}\sum _{m=1}^M\ell ({\xi }_{J_m},x)\approx \mathcal{L}(\Xi ,x).$$

Re-drawing $J$ i.i.d. each call makes $\tilde{\mathcal{L}}$ an unbiased estimator; by the CLT it is approximately Gaussian:

$$p(\tilde{\mathcal{L}}(x)\mid \mathcal{L}(\Xi ,x))\approx \mathcal{N}(\tilde{\mathcal{L}}(x);\mathcal{L}(\Xi ,x),{\sigma }^2),{\sigma }^2\propto 1/M.$$

Batching thus provides a knob ($M$) trading computational precision against cost, and evaluations at different $x$ are disturbed by independent Gaussian noise (batches re-drawn each request). Signal-to-noise ratios below one are common in deep learning.

This Gaussian noise explicitly introduces a likelihood into the computation, naturally motivating a probabilistic treatment — and explains why efficient classical methods (tuned for Dirac likelihoods) struggle in the noisy setting.

Examples

Two robots doing gradient descent (Exercise 25.2)

Two wheeled robots on a hill do “gradient descent” on potential-energy density $f(x_i)=\mathbb{E}(x_i)/m=g\cdot h(x_i)$ with a fixed step $\alpha =0.1$, stepping $x_{i+1}=x_i-\alpha \nabla f(x_i)$. One uses SI units ($g=9.81{\text{m/s}}^2$), the other Imperial ($g=32.19{\text{ft/s}}^2$). Because a fixed step size interacts with the units/scaling of the gradient, the two identical-in-spirit robots take different physical steps and reach different energies — an intuition for why fixed step sizes (unlike an adaptive/perfect line search) are problematic and hide unit-dependent assumptions.

Gaussian-process view of ERM (Exercise 26.1)

A basic GP regression model — data $Y=[y_1,\dots ,y_N]$ produced by latent $f$ at $X=[x_1,\dots ,x_N]$ under i.i.d. Gaussian likelihood $p(Y\mid f)=\mathcal{N}(Y;f_X,{\sigma }^2{I}_N)$ and GP prior $p(f)=\mathcal{G}\mathcal{P}(f;\mu ,k)$ — is itself an optimisation problem with a loss of the ERM form. Its MAP posterior mean solves that loss; choosing the prior/likelihood corresponds to choosing regulariser $r$ and per-datum loss $\ell$.

Connections

• Instantiates Computation as Probabilistic Inference for the first nonlinear task; the Dirac→explicit-likelihood move is the crux.
• The two per-iteration decisions are agent actions (The Numerical Agent); step-size selection is developed in Probabilistic Step-Size Selection and Line Searches and direction selection in First- and Second-Order Optimisation Methods.
• The batch-noise likelihood mirrors the observation model of Gaussian Process Regression; the GP surrogate along a line reuses Gauss-Markov Processes and SDEs.
• Global optimisation (The Global Optimisation Problem) targets the global $x_{\ast }$ of a multimodal, expensive black box — a fundamentally different problem.

See Also

• Probabilistic Step-Size Selection and Line Searches — the line-search sub-problem made probabilistic.
• First- and Second-Order Optimisation Methods — choosing the search direction $d_i$.
• The Global Optimisation Problem — from local modes to the global optimum.
• Computation as Probabilistic Inference — Dirac vs. explicit likelihood.