Probabilistic Step-Size Selection and Line Searches

Summary

A line search decides the step size $\alpha$ along a fixed direction by probing the univariate objective $f(\alpha )$ and its projected gradient $f^{\prime }(\alpha )$, stopping when the Wolfe conditions hold. Under batch noise these deterministic ingredients break; the probabilistic line search of Mahsereci & Hennig replaces every non-probabilistic element by its Bayesian counterpart: cubic-spline interpolation becomes GP regression with an integrated-Wiener kernel, the bisection/evaluation rule becomes an expected-improvement decision, and the Boolean Wolfe test becomes a probability of the Wolfe conditions (a bivariate-normal integral). The same probabilistic reasoning yields runtime rules for batch size and early stopping (Ch. 27).

Overview

In the linear problem $Ax=b$ the step size was a trivial analytic ratio once $z_i=A{d}_i$ was known; in the nonlinear setting it is not. Line searches are considered an “easier”, nearly-solved inner-loop problem in the noise-free world, but under significant computational noise they become genuinely hard (Thm. 25.3, Exercise 25.2 show step size is decisive). Ch. 26 is a case study: build a classical line search, then carefully replace each non-probabilistic aspect by a probabilistic equivalent, adding essentially no overhead. Ch. 27 generalises the theme — controlling other optimiser hyperparameters (batch size, stopping) by probabilistic estimates.

Main Content

The Wolfe termination conditions

(Weak and strong) Wolfe conditions

With constants $0\le c_1<c_2\le 1$, a step length $\alpha$ is acceptable if

$$f(\alpha )\le f(0)+c_1\alpha f^{\prime }(0)\text{(sufficient decrease / Armijo)},\text{\hspace{1em}(26.5)}$$ $$f^{\prime }(\alpha )\ge c_2{f}^{\prime }(0)\text{(weak curvature condition)}.\text{\hspace{1em}(26.6)}$$

The strong Wolfe conditions replace (26.6) by $|f^{\prime }(\alpha )|\le c_2|f^{\prime }(0)|$ (26.8), adding an upper bound on the gradient. Here $f(0),f^{\prime }(0)$ are the value and projected gradient at the start of the search. The Armijo condition demands the function lie sufficiently below its initial value (linear decrease slope $c_1$); the curvature condition demands the gradient increase beyond its initial value. Practical lenient choices: $c_1=10^{-4}$, $c_2=0.9$.

The Wolfe conditions do not guarantee the true optimum lies in the accepted bracket, nor that the chosen step is close to ${\alpha }_{\ast }$; they merely rule out pathological behaviour (increasing values, tiny steps) and, combined with direction rules, give guarantees on $d_{i+1}$ (e.g. for BFGS the curvature condition guarantees $d_{i+1}$ is a descent direction). Requiring $c_2>c_1$ is necessary for acceptable steps to exist (Exercise 26.2).

Classical search by cubic-spline interpolation

The classical evaluation rule builds cubic local approximations of $f(\alpha )$ from collected $f,f^{\prime }$ values, stepping to a local minimum or an extrapolation point (Wahba; Nocedal & Wright §3.3). Starting from $f_0,f_0^{\prime }$, the linear guess $\hat{f}(\alpha )=f_0+\alpha f_0^{\prime }$ has no minimum, so a first step ${\alpha }_1$ is set ad hoc (e.g. the previous search’s terminal step). Given four numbers $f_0,f_1,f_0^{\prime },f_1^{\prime }$, a unique cubic $\hat{f}(\alpha )=a{\alpha }^3+b{\alpha }^2+\alpha f_0^{\prime }+f_0$ interpolates them (26.9), with coefficients (26.10) and its quadratic derivative minimised at ${\alpha }_2=(-b+\sqrt{b^2-3a{f}_0^{\prime }})/(3a)$. If the new point satisfies Wolfe, stop; else bisect the bracketing interval by the sign of $f^{\prime }({\alpha }_2)$ and re-interpolate. This procedure is brittle to noise: a single erroneous bisection (from a noisy gradient sign) sends the search down a dead-end from which it cannot recover (Fig. 26.3).

Probabilistic line search: three replacements

The three probabilistic substitutions

The classical routine has three non-probabilistic ingredients replaced (Mahsereci & Hennig 2015):

1. Spline interpolation → GP regression extended to noisy observations;
2. Deterministic bisection → a candidate-set + utility rule (no region can be “bisected away” with certainty);
3. Boolean Wolfe test → a probability of having found a suitable point.

All three are unified by casting spline interpolation as the noise-free limit of GP regression.

(1) Cubic splines as the integrated Wiener process

The SDE $\mathrm{d}[f,f^{\prime }{]}^{\top }=[\begin{array}{cc}0& 1\\ 0& 0\end{array}][f,f^{\prime }{]}^{\top }\mathrm{d}\alpha +[0,q{]}^{\top }\mathrm{d}{\omega }_t$ (26.11) — the integrated Wiener process (see Gauss-Markov Processes and SDEs) — has kernel $\mathrm{cov}(f(a),f(b))={\theta }^2(\frac{1}{3}{\min }^3(a,b)+|a-b|\frac{1}{2}\min (a,b))$. Its GP posterior mean is a piecewise-cubic polynomial that, in the noise-free limit $\Lambda \to 0$, reverts exactly to the classical cubic spline. Conditioning on nontrivial $[f(0),f^{\prime }(0)]=[f_0,f_0^{\prime }]$ gives mean $[\mu (\alpha ),{\mu }^{\prime }(\alpha )]=[f_0+f_0^{\prime }\alpha ,f_0^{\prime }]$ and the joint value/derivative kernel (26.13, with ${\alpha }_{\square }:=\min ({\alpha }_a,{\alpha }_b)$)

$$\left[\begin{array}{cc}{k}_{{\alpha }_a{\alpha }_b}& k_{{\alpha }_a{\alpha }_b}^{\partial }\\ \partial k_{{\alpha }_a{\alpha }_b}& \partial k_{{\alpha }_a{\alpha }_b}^{\partial }\end{array}\right]=q^2\left[\begin{array}{cc}\frac{1}{3}{\alpha }_{\square }^3-\frac{1}{2}{\alpha }_{\square }^2+{\alpha }_a{\alpha }_b{\alpha }_{\square }& -\frac{1}{2}{\alpha }_{\square }^2+{\alpha }_a{\alpha }_{\square }\\ -\frac{1}{2}{\alpha }_{\square }^2+{\alpha }_b{\alpha }_{\square }& {\alpha }_{\square }\end{array}\right].$$

The GP posterior mean/covariance (26.14–26.15) follow from standard Gaussian Process Regression with the noisy likelihood (Model 26.3):

Model 26.3 — Gaussian likelihood for values and gradients

$$p(Y\mid f)=\mathcal{N}(Y;[f({\alpha }_1),\dots ,f({\alpha }_K),f^{\prime }({\alpha }_1),\dots ,f^{\prime }({\alpha }_K){]}^{\top },\Lambda ),$$

$Y\in {\mathbb{R}}^{2K}$ stacks values (first $K$) then gradients, with spd noise covariance $\Lambda \in {\mathbb{R}}^{2K\times 2K}$ whose block structure allows value/gradient noise to co-vary at one node ${\alpha }_i$ (correlation ${\rho }_i$) but assumes noise at different locations is independent (correct when batches are re-drawn per evaluation, Eq. 26.3). Since $\Lambda$ is block-diagonal the posterior can be computed by $2\times 2$ Kalman filtering/smoothing, at cost a constant multiple of the classical routine.

(2) Selecting evaluation nodes by expected improvement

In the noisy setting no region can be bisected away, so the search maintains a finite candidate set $\tau =[{\tau }_1,\dots ,{\tau }_L]$: (i) an extrapolation candidate ${\tau }_1={\alpha }_{\max }+r_i$ (with growth policy $r_i=1$, $r_i=i$, or $r_i=2^i$), plus (ii) all local minima of the posterior mean $\nu (\alpha )$ in $[0,{\alpha }_{\max }]\setminus \{{\alpha }_i\}$. The next node maximises a utility $\hat{\alpha }=\arg {\max }_{{\tau }_{\ell }}\{u({\tau }_{\ell })\}$, e.g. the expected improvement over the best previous mean $\eta ={\min }_i\{\nu ({\alpha }_i)\}$:

Expected improvement along the line (26.16)

$$u_{\text{EI}}(\tau )={\mathbb{E}}_{p(f(\tau )\mid Y)}(\min \{0,\eta -f(\tau )\})=\frac{\eta -\nu (\tau )}{2}(1+\mathrm{erf}\frac{\eta -\nu (\tau )}{\sqrt{2{\kappa }_{\tau \tau }}})+\sqrt{\frac{{\kappa }_{\tau \tau }}{2\pi }}\exp (-\frac{(\eta -\nu (\tau ){)}^2}{2{\kappa }_{\tau \tau }}),$$

where $\nu (\tau ),{\kappa }_{\tau \tau }$ are the posterior mean and variance at $\tau$. In practice the product $u_{\text{EI}}\cdot p_{\text{Wolfe}}$ works well. (See Acquisition Functions — this is the univariate ancestor of EI.)

(3) Probabilistic Wolfe conditions

Wolfe conditions as a bivariate-normal probability

The weak Wolfe conditions are a linear projection of $(f,f^{\prime })$: they require $a_{\alpha },b_{\alpha }\ge 0$ where

$$\left[\begin{array}{c}{a}_{\alpha }\\ b_{\alpha }\end{array}\right]=\left[\begin{array}{cccc}1& c_1\alpha & -1& 0\\ 0& -c_2& 0& 1\end{array}\right]\left[\begin{array}{c}f(0)\\ f^{\prime }(0)\\ f(\alpha )\\ f^{\prime }(\alpha )\end{array}\right]\ge \left[\begin{array}{c}0\\ 0\end{array}\right].$$

By closure of Gaussians under linear maps (Gaussian Distributions and Algebra), the GP posterior on $(f,f^{\prime })$ induces a bivariate Gaussian $p(a_{\alpha },b_{\alpha })=\mathcal{N}([a_{\alpha },b_{\alpha }{]}^{\top };[m_{\alpha }^a,m_{\alpha }^b{]}^{\top },[\begin{array}{cc}{C}^{aa}& C^{ab}\\ C^{ba}& C^{bb}\end{array}])$ with

$$m_{\alpha }^a={\nu }_0-{\nu }_{\alpha }+c_1\alpha {\nu }_0^{\prime },m_{\alpha }^b={\nu }_{\alpha }^{\prime }-c_2{\nu }^{\prime }(0),$$ $$C_{\alpha }^{aa}={\kappa }_{00}+(c_1\alpha {)}^2{\kappa }_{00}^{\partial \partial }+{\kappa }_{\alpha \alpha }+2(c_1\alpha ({\kappa }_{00}^{\partial }-\partial {\kappa }_{0\alpha })-{\kappa }_{0\alpha }),C_{\alpha }^{bb}=c_2^2{\kappa }_{00}^{\partial \partial }-2c_2\partial {\kappa }_{0\alpha }^{\partial }+\partial {\kappa }_{\alpha \alpha }^{\partial },\text{ etc.}$$

The probability that the weak Wolfe conditions hold is the bivariate-normal integral

$$p(a_{\alpha }\ge 0\wedge b_{\alpha }\ge 0)={\int }_{-m_{\alpha }^a/\sqrt{C_{\alpha }^{aa}}}^{\infty }{\int }_{-m_{\alpha }^b/\sqrt{C_{\alpha }^{bb}}}^{\infty }\mathcal{N}([\begin{array}{c}a\\ b\end{array}];0,[\begin{array}{cc}1& {\rho }_{\alpha }\\ {\rho }_{\alpha }& 1\end{array}])\mathrm{d}a\mathrm{d}b,{\rho }_{\alpha }=\frac{C_{\alpha }^{ab}}{\sqrt{C_{\alpha }^{aa}{C}_{\alpha }^{bb}}}.$$

The point is accepted once this probability crosses a threshold $c_W$ (e.g. 0.3) after an evaluation. The strong condition adds a linear upper limit $\bar{b}=-2c_2{\nu }_0^{\prime }$ on $b_{\alpha }$ (26.17).

The completed method (Algorithm 26.1, probLineSearch) operates on scaled pairs $\mathbf{f}(t)=[(f(t)-f(0))/f^{\prime }(0),f^{\prime }(t)/f^{\prime }(0)]$ with $t=\alpha /{\alpha }_{i-1}$, avoiding hyperparameters; it aborts after a fixed budget (~10 evaluations) with a rare fall-back to the posterior-mean minimum. It runs robustly on MLPs and logistic regression on MNIST/CIFAR10 (Fig. 26.6). Uncertain observations require additional observables: the noise variances ${\sigma }_{f_i}^2,{\sigma }_{f_i^{\prime }}^2$ (elements of $\Lambda$) are absent classically and must be estimated at runtime from within-batch statistics

$$S_i=\frac{1}{M}\sum _m{\ell }_m^2({\alpha }_i),S_i^{\prime }=\frac{1}{M}\sum _m(d_i^{\top }\nabla {\ell }_m({\alpha }_i){)}^2,{\sigma }_{f_i}^2=\frac{S_i-y_i^2}{M-1},{\sigma }_{f_i^{\prime }}^2=\frac{S_i^{\prime }-(y_i^{\prime }{)}^2}{M-1}.\text{\hspace{1em}(26.18)}$$

Controlling other hyperparameters by probabilistic estimates (Ch. 27)

Optimal batch size for SGD

With $g_M(x)\sim \mathcal{N}(\nabla \mathcal{L}(x),\frac{1}{M}\Sigma (x))$ (27.1), $\Sigma$ the gradient-element covariance whose diagonal is estimated by $S=\frac{1}{M}{\sum }_j\nabla \ell ({\xi }_j,x{)}^{.2}-g_M(x{)}^{.2}$ (27.2), assume $\mathcal{L}$ is $L$-Lipschitz-smooth. The per-step expected gain is

$$\mathbb{E}(G)=({\alpha }_i-\frac{L{\alpha }_i^2}{2})\Vert \nabla \mathcal{L}(x_i){\Vert }^2-\frac{L{\alpha }_i^2}{2M}\mathrm{tr}\Sigma ,$$

using $\mathbb{E}(\Vert g_i{\Vert }^2)=\Vert \nabla \mathcal{L}(x_i){\Vert }^2+\mathrm{tr}\Sigma /M$. Since cost is linear in $M$, maximising expected gain per cost $\mathbb{E}(G)/M$ gives

$$M_{\ast }=\frac{2L\alpha }{2-L\alpha }\frac{\mathrm{tr}\Sigma }{\Vert \nabla \mathcal{L}(x_i){\Vert }^2}.\text{\hspace{1em}(27.3)}$$

Under a scalar-Hessian approximation ($B\approx hI$, optimal rate $\alpha =1/h$) and energy-type risks (${\mathcal{L}}_{\ast }\approx 0$) this simplifies to the upper bound $M_{\ast }\le \alpha \mathrm{tr}\Sigma /\mathcal{L}(x_i)$ (27.4). The tuning heuristic again involves $\mathrm{tr}\Sigma$, a quantity absent in the noise-free case, estimated cheaply at runtime.

Statistical early-stopping test

In the noisy case $\nabla \mathcal{L}=0$ never holds exactly; stop when we cannot rule out being at the population optimum. With $p(\nabla \mathcal{L}(x)\mid f)=\mathcal{N}(\nabla \mathcal{L};\nabla f(x),\Sigma (x)/K)$, the evidence under $\nabla f(x)=0$ is $p(\nabla \mathcal{L}(x)\mid 0)=\mathcal{N}(\nabla \mathcal{L};0,\Sigma (x)/K)$. Assuming independence across gradient elements and reusing $S$ (27.2), a log-likelihood-ratio test $\log p(\nabla \mathcal{L}\mid 0)-{\mathbb{E}}_{p(\nabla \hat{\mathcal{L}}\mid 0)}(\cdot )>0$ reduces to

$$1-\frac{K}{N}\sum _{i=1}^N\left(\frac{[\nabla \mathcal{L}(x){]}_i}{S_i(x)}\right)>0,$$

i.e. stop when the average gradient element lies within its “error bar” $S$. Here computational and empirical (population-vs-empirical-risk) uncertainty overlap and need not be distinguished.

Examples

Erroneous bisection under SNR = 1

With gradient noise $p(y^{\prime }(\alpha )\mid f^{\prime }(\alpha ))=\mathcal{N}(y^{\prime }(\alpha );f^{\prime }(\alpha ),{\sigma }^2)$ and $\sigma \approx |f^{\prime }(0)|$ (a realistic SNR of 1 in big data), one may observe $y^{\prime }({\alpha }_1)>0$ while the true $f^{\prime }({\alpha }_1)<0$. A classical line search bisects the wrong sub-interval and is permanently derailed (Fig. 26.3). The probabilistic line search instead reverts its GP mean toward the prior, yielding a smoother interpolant and a probability (not a certainty) of Wolfe satisfaction, so no irreversible decision is taken.

Connections

• Builds directly on The Local Optimisation Problem (the projected univariate sub-problem, ERM batch noise).
• The integrated-Wiener prior is a Gauss-Markov SDE; inference is Gaussian Process Regression with a joint value/gradient likelihood; the Wolfe projection uses Gaussian closure under linear maps.
• The line-search EI (26.16) is the univariate special case of Expected Improvement; value-of-information appears as in Bayesian Quadrature.
• Curvature-condition guarantees feed BFGS descent directions.

See Also

• The Local Optimisation Problem — the setting and the two per-iteration decisions.
• First- and Second-Order Optimisation Methods — the outer-loop direction decision, using Wolfe guarantees.
• Acquisition Functions — EI and value-of-information at global scale.
• Gauss-Markov Processes and SDEs — the integrated Wiener process behind cubic splines.
• The Global Optimisation Problem — the global counterpart, where the same value-of-information logic drives whole-evaluation choices.