mod runtime_distribution

module runtime_distribution

Run-time distributions: what a search’s time to target supports. Run-time distributions for a search that finds the answer eventually.

A global optimiser that reaches the minimum given enough time is a Las Vegas algorithm: always right, randomly slow. What characterises one is the distribution of its time to a target, not the quality it reports at a budget somebody picked. The two answer different questions and disagree exactly where a funnel-exchange move earns its place, because escaping a funnel raises the spread and a mean at fixed budget rewards whichever arm is reliably mediocre.

Three things follow, and each is a number this module computes rather than an opinion:

• How many runs a comparison needs before it can resolve anything. A success rate near a quarter needs runs in the dozens to place to a few points, and comparisons at eight runs resolve nothing.

• Whether running replicas in parallel buys time proportionally. For a time-to-target that is exponential the answer is yes; for a shifted exponential the offset is dead weight every replica pays and the speedup has a ceiling, which is parallel_speedup and its limit speedup_ceiling.

• Whether restarting beats continuing, which is a question about the tail and not about the mean.

Nothing here runs a search. It takes the times a search reported, including the runs that never arrived, and says what they support.

Types

type RunTime

One run’s outcome: evaluations spent reaching the target, or None when the run ended without reaching it.

The censored runs are the ones a mean would quietly drop, and they are the informative half when the target is rare.

Functions

fn offset_is_resolved(runs: &[RunTime]) -> bool

Whether an offset estimate is worth quoting.

The offset’s standard error goes as (1/(nlambda)) in the arrivals, so it is placed to within a tenth of itself only once the arrivals are numerous relative to the excess-to-offset ratio. Below that the estimate is still moving and a ceiling drawn from it is a property of the sample rather than of the search.

fn parallel_speedup(offset: f64, rate: f64, processors: usize) -> f64

Expected time to target when processors independent runs race.

For a shifted exponential the minimum of n draws is again shifted exponential with the same offset and n times the rate, so the expectation is (mu + 1/(nlambda)). Everything past the offset divides; the offset does not.

fn reached_quantile(runs: &[RunTime], quantile: f64) -> Option<u64>

Empirical quantile of the runs that reached the target.

fn resolvable_shortfall(hits_a: usize, hits_b: usize, runs: usize) -> f64

Maximum shortfall in successes that runs cannot resolve.

Two rates measured over the same number of runs differ by a standard error of (sqrt{2hat p(1-hat p)/n}) at the pooled rate. Two of those, in runs, is the bound below which a difference is a sample.

fn runs_for_resolution(rate: f64, half_width: f64) -> usize

Runs needed to place a success rate within half_width, at about ninety-five per cent confidence.

The usual normal interval: (n = z^2 p(1-p)/delta^2). A rate near a half is the expensive one to measure, so an unknown rate should be budgeted at 0.5. This is the function that says whether a comparison was ever going to conclude anything.

fn shifted_exponential_fit(runs: &[RunTime]) -> Option<(f64, f64)>

Shifted-exponential fit to the runs that reached the target.

Returns the offset and the rate beyond it.

The offset is the awkward one and a caller has to know why. Its maximum-likelihood estimate is the smallest observed time, an extreme-order statistic: it can only fall as runs are added, so the estimate drifts down and every quantity drawn from it, the speedup ceiling above all, drifts up. Measured on LJ38 the offset read 4629 over 96 arrivals and 2815 over 384, taking the ceiling from 2.84 to 4.89 on the same search, and the two arms swapped which of them had the lower one.

This returns the bias-corrected estimate, (t_{(1)} - (bar t - t_{(1)})/(n-1)), which removes the leading bias but not the drift. An offset read off tens of arrivals is not a converged number and must not be quoted as one; offset_is_resolved is the guard.

Censored runs are excluded, which biases the fit optimistic when most runs never arrive; success_rate says whether to trust it at all.

fn speedup_ceiling(offset: f64, rate: f64) -> f64

Speedup no number of processors can exceed.

((mu + 1/lambda)/mu), the limit of parallel_speedup. An offset of zero is the exponential case and returns infinity, which is the honest answer: there is no ceiling, speedup is linear in the processors. A large offset relative to the mean is the warning that cores are being spent on a queue every one of them has to stand in.

fn success_rate(runs: &[RunTime]) -> f64

Fraction of runs that reached the target.