Adaptive capping

Adaptive capping reduces the cost of algorithm configuration by ending an evaluation when a valid bound already rules out winning the comparison. For nonnegative runtimes, completed runs and elapsed time in the current run can provide a lower bound on the final cost. ParamILS distinguishes trajectory-preserving capping from a more aggressive heuristic policy.^[ref]

Consider an original comparison of mean runtime over $N=4$ fixed runs. The incumbent has mean $c_{\ast }=5$ seconds, or total $20$ seconds. A candidate has completed runs taking $6$ and $7$ seconds, and its third run has already taken $8$ seconds. Even if all remaining work took zero time, the final mean would satisfyContinuing that candidate cannot improve this comparison. The partial total itself supplies the certificate; no prediction of the remaining runtime is needed.

By contrast, after only the first two runs, their observed mean is $13/2=6.5>5$, but rejecting solely on that partial mean would be invalid: the four-run lower bound is only $13/4=3.25$. Two sufficiently fast remaining runs could still win. The denominator must correspond to the comparison objective.

A censored algorithm runtime is therefore not an observed completed runtime. Record the cutoff and what bound it establishes. Timeout penalties, changing instance sets or non-runtime objectives require a bound compatible with their own scoring rules. A heuristic early-stopping rule may be useful without preserving the same search decisions as full evaluation.

A censored algorithm runtime is an evaluation that ends without observing the algorithm's actual completion time. A timeout or adaptive capping limit can establish that the run had not finished by the cutoff, supplying right censoring rather than an exact completed runtime. The ParamILS capping analysis uses such elapsed-time information to bound comparisons without finishing every run.^[ref]

Write $T$ for completion time and $C$ for a stopping limit. A simple record iswhere $\delta =1$ means completion was observed. The event flag is essential: the same stored duration can mean a completed run or only a lower bound on a still-running computation.

For an original example, two completed runs take $2$ and $5$ seconds and a third is stopped unfinished at $10$ seconds. Averaging the stored durations gives $17/3\approx 5.67$ seconds, but that is only a lower bound on the mean of the actual completion times. If the third would take $40$ seconds, the true mean is $47/3\approx 15.67$ seconds. Discarding it entirely gives $3.5$ seconds and removes the difficult run from the comparison.

Keep exact observations, cutoff information and any timeout penalty separate. A penalized benchmark score may deliberately assign a stated cost to a timeout; that score is not an observation of $T$. Estimating completion-time distributions additionally requires assumptions about how stopping limits were chosen, particularly when the limits depend on earlier performance.