mod terminate

module terminate

Stopping a relaxation when its answer is no longer in doubt.

A local relaxation runs to an iteration cap, and most of those iterations are spent near convergence buying very little energy. For the great majority of trials the question being asked is not “what is the exact minimum” but “does this beat the incumbent”, and that question is settled long before the relaxation is.

Treating the unconverged limit as an unknown with a distribution, rather than as something you must compute exactly, is what probabilistic numerics asks of an iterative solver. The limit of a quasi-Newton descent is estimated from the decrements it has produced so far, and the relaxation stops as soon as the estimate says the answer to the caller’s question is decided.

The model

Near a minimum a quasi-Newton method converges linearly on the energy: the decrements d_k = e_{k-1} - e_k fall by roughly a constant factor. If they do, the energy still to be gained is a geometric tail,

e_inf = e_k - d_k r / (1 - r),   r = the ratio the decrements are falling by

and the spread of the observed ratios says how much to trust it. The ratio is estimated in log space, where a multiplicative process is additive and a Gaussian on it is not obviously wrong.

Measured, and it does not pay here

Wired to the screening pass at 75 points and three million evaluations it scored 0 seeds in 8, against 13 in 24 for the same driver without it. It fired on 107520 of 108893 hops and saved 857049 relaxation iterations, so the saving was real and the search was worse for it.

Stopping nearly every screen means the chain acts on limits extrapolated from a handful of decrements, and the screen’s job is to decide which trials deserve a full relaxation. Buying hops by degrading that decision is a bad trade at this ratio: hops cost about thirty evaluations and a missed crossing costs the run.

Kept, tested, and off. It is a correct estimator of a limit; the fault is in spending its output on a decision this sensitive. A caller with a cheaper objective or a coarser question may find it pays.

What it will not do

It never stops before Terminator::min_iters, because two decrements estimate a ratio and no decrements estimate nothing, and it never reports a limit when the decrements are not falling (r >= 1), because then the tail is not geometric and the extrapolation would be an invention rather than an estimate.

Structs and Unions

struct Terminator

Watches a decreasing sequence and says when its limit is decided.

min_iters: usize

Iterations before any early stop is considered.

confidence: f64

Standard deviations of headroom required to call the question settled.

The estimate is an extrapolation, so stopping on the mean alone stops early and wrong. Two standard deviations of margin is the difference between saving iterations and losing minima.

steps: usize

Values seen.

Implementations

impl Terminator

Functions

fn limit(&self) -> Option<(f64, f64)>

Estimated limit and its standard deviation, if the tail is geometric.

None when there is too little to go on, or when the decrements are not falling, in which case the sequence is not in its linear regime and extrapolating it would be invention.

fn new(min_iters: usize, confidence: f64) -> Self

A terminator that waits min_iters and requires confidence sigma.

fn observe(&mut self, e: f64)

Records the energy after another iteration.

fn reset(&mut self)

Forgets the sequence, for reuse on the next relaxation.

fn settled_above(&self, target: f64) -> bool

Whether the sequence can be stopped because it will not reach target.

True only when the estimated limit sits confidence standard deviations above the target: the caller wanted to know whether this relaxation beats an incumbent, and it will not.

Traits implemented

impl Default for Terminator