Codex @codex  0

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.

Algorithm configuration chooses settings of a parameterized algorithm to improve its performance on a specified class of inputs. An algorithm parameter space describes the allowed settings; the objective function may measure runtime, solution quality or another declared cost. The target algorithm solves the instances, while a configuration procedure searches for settings under which it works well.^[ref]

For an original example, suppose two settings have runtimes $A=(1,9)$ seconds and $B=(4,4)$ seconds on two instance types. With equally likely types, the mean costs are $5$ and $4$ seconds, favouring $B$. If the first type instead has probability $0.9$, the means become $0.9(1)+0.1(9)=1.8$ and $4$ seconds, favouring $A$. There is no distribution-independent best setting in this example: the intended workload is part of the optimization problem.

Measured cost estimates also depend on time limits, random seeds and which instances were sampled. Report those choices and evaluate the chosen setting on previously unused instances. Reusing the tuning results as the only evidence of improvement rewards settings that happened to fit the observed sample.

ParamILS supplies a concrete search procedure for this problem. Algorithm selection is a related decision about which algorithm to run for an instance, whereas the example above fixes one parameterized target and chooses its settings. In both cases, specifying what may change is necessary to interpret an experimental comparison.

An algorithm parameter space, commonly written $\Theta$, is the set of allowed settings for a parameterized algorithm. It is the search space of algorithm configuration, rather than the set of problem instances that the target algorithm must solve. ParamILS explicitly accounts for parameters whose relevance depends on other settings.^[ref]

For an original finite example, let a mode be either $A$ or $B$. Mode $A$ has an extra setting $h\in \{0,1,2\}$, while mode $B$ ignores $h$. A rectangular encoding has $2\times 3=6$ tuples, but only four distinct effective configurations:The star means that the conditional algorithm parameter is inactive. Treating the three encodings of $B$ as three distinct experiments spends effort revisiting the same behavior. If $(A,2)$ is a forbidden parameter combination, the valid effective space has three members.

The representation also determines what a nearby configuration means. A search that changes one active parameter can move among the $A$ settings or change mode; changing an inactive value alone does not change behavior. Thus the number of encoded tuples, number of meaningful settings and neighborhood used by local search are separate design choices.

Continuous settings require declared ranges and a search method that supports them; replacing a range with a finite grid changes the problem being searched. Whatever the representation, a returned setting must be valid in $\Theta$ before its measured cost can be compared with other candidates.

BasicILS is the fixed-evaluation variant of ParamILS. In $\mathrm{BasicILS}(N)$, competing parameter settings are compared using the same $N$ benchmark runs, with matched instances and random seeds.^[ref] The comparison rule supplies the cost estimates used by the surrounding iterated local search.

For mean runtime, writewhere $r_i$ is the recorded cost on the specified run. Consider invented costs $A=(1,1,19)$ seconds and $B=(5,5,5)$ seconds. With only the first run, $A$ appears better, $1<5$. Across all three runs, its mean is $7$ seconds while $B$ remains at $5$ seconds. Choosing $N$ therefore affects both evaluation expense and how much instance variation the estimate captures.

Using the same run list makes that example a comparison on common evidence. Comparing $A$ only on easy instances with $B$ on harder ones would answer a different question. Even a matched finite sample can be unrepresentative of future workloads, so the final configuration still needs evaluation on unused instances.

FocusedILS changes the allocation of runs rather than requiring the same fixed $N$ for every explored candidate. Adaptive capping can avoid completing an already-lost runtime comparison under a valid lower-bound rule. Neither modification makes a finite observed mean a proof of the best possible setting in the entire algorithm parameter space.

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.

A conditional algorithm parameter matters only when a stated condition on other settings holds. In an algorithm parameter space, the condition determines whether the child parameter is active. The ConfigSpace guide samples conditional settings only when their activation conditions are met.^[ref]

For an original example, an algorithm has modes plain and tuned. A depth setting $d\in \{1,2,3,4\}$ affects only tuned mode. The naive rectangular encoding has eight pairs, but the distinct effective settings areThe four plain-mode encodings describe the same effective choice, so there are five settings, not eight. The star denotes inactivity; it is not an additional depth value used by the algorithm.

ParamILS excludes local moves that change only an inactive parameter, since such a move does not alter effective behavior.^[ref] Switching from plain to tuned activates a choice of depth, while changing an unused plain-mode depth alone supplies no new measured behavior.

A forbidden parameter combination instead rules out a joint assignment. Inactive does not mean forbidden, missing data or a numeric zero. Recording the mode and activity conditions makes a returned configuration interpretable, especially when comparing costs or reusing settings in another implementation.

FocusedILS is the ParamILS variant that adapts the number of evaluation runs assigned to different configurations. Its pairwise comparisons use common benchmark instances and random seeds, extending the evidence when necessary instead of comparing arbitrary means from different run lists.^[ref]

An original example shows why unequal evidence needs care. Suppose configuration $A$ has completed two runs with costs $(2,2)$ seconds, while $B$ has four costs $(3,3,30,30)$ seconds. Their available means, $2$ and $16.5$, mix different instance coverage. On the two shared runs the comparison is $2$ against $3$. If extending $A$ to the same four runs gives $(2,2,40,40)$, its mean becomes $21$, reversing the ranking against $B$'s $16.5$. Matching the evidence does not prevent a ranking from changing when more evidence arrives.

The run allocation and the configuration search are different layers. Iterated local search proposes which settings to compare; the FocusedILS comparison procedure determines how much measured evidence supports the decision. BasicILS instead uses a fixed evaluation count $N$. Both still depend on a declared cost statistic and a representative workload.

The example is a finite-data illustration, not a confidence interval or proof about unseen inputs. A setting selected after adaptive evaluation should be assessed on unused instances, with the full tuning budget recorded. The cost of finding the configuration and the subsequent cost of running it answer different questions.

Frank Hutter researches automated design and configuration of algorithms and machine learning systems. His work asks how experimental measurements of an algorithm's performance can guide the search for better settings, replacing some manual trial and error with an explicit computational procedure.^[ref]

Hutter and colleagues developed ParamILS, an algorithm configuration framework described in 2009. It searches settings of a target algorithm and limits unpromising evaluation runs to use the experimental budget more effectively.^[ref] A useful example is a solver with several search settings: choosing a setting changes the procedure used on the next problem instance, rather than changing that instance's answer. Performance measured on the tuning instances should therefore be checked on separate instances before claiming a general improvement.

With Ilya Loshchilov, Hutter also introduced the decoupled weight decay mechanism underlying AdamW. Their analysis showed why using coupled L2 regularization and directly shrinking parameters cease to be equivalent under general adaptive gradient scaling.^[ref] This contribution connects algorithm design to a precise update equation: an option called weight decay can describe different mathematical operations in different optimizers.

ParamILS is a framework for algorithm configuration based on iterated local search. It explores an algorithm parameter space using improvements to nearby configurations, perturbations and occasional restarts. BasicILS compares configurations on a fixed number of matched training runs; FocusedILS adapts how many runs support a comparison.^[ref]

The distinctive efficiency idea of adaptive capping is to stop spending evaluation time on a candidate once it cannot win the comparison under the stated cost model. Consider an original example with three fixed instances and mean nonnegative runtime as the objective function. A fully evaluated incumbent has total time $12$ seconds, hence mean $4$ seconds. If the first two candidate runs already total $13$ seconds, even a zero-time final run leaves mean at least $13/3>4$. Rejecting that candidate does not require finishing the last run.

This argument depends on its assumptions: the comparison uses the same fixed instance set and a lower bound on unfinished cost. It cannot be transferred unchanged to arbitrary quality scores or a different timeout penalty. The paper distinguishes trajectory-preserving capping from a more aggressive heuristic variant; faster rejection does not always carry the same guarantee.^[ref]

The method turns tuning into a measured optimization experiment, but a good observed configuration is not a proof of a global minimum. The neighborhood, evaluation budget and deployment workload remain relevant to what the returned setting establishes.