Choosing How Long to Wait: Survival-Model Surrogates for Multi-Objective Search with Capped Evaluations

When tuning a neural network for both speed and quality, some measurements are cheap and some are not. Inference latency or parameter count takes seconds. "How long does training take to reach the target accuracy" can take hours, and it may never finish. Recent multi-objective Bayesian optimization methods already let the optimizer measure each objective separately: it asks "which objective, at which design?" instead of always paying for every measurement at once. These methods still assume that a slow measurement, once started, runs to completion and returns an exact number. In practice we stop slow runs early. The result is a right-censored observation, meaning we learn only that the run took longer than the time we allowed. How long to allow is itself a decision with a price.

We propose to treat the slow objective as what it actually is: a time-to-event quantity. We model it with a proportional hazards survival model, the standard tool for censored time-to-event data. The optimizer then chooses three things together: a design, an objective, and a time cap. The survival model supplies two quantities that current methods lack. The first is the expected cost of a capped run, which is the area under the predicted survival curve up to the cap. The second is a proper way to learn from runs that hit the cap. The claim is specific. On benchmarks where one objective is time-to-target, picking the cap jointly with the design and objective, and pricing it from a calibrated survival curve, reaches a given Pareto-front quality at lower total wall-clock cost than decoupled methods that use fixed caps or parametric censored surrogates.

Where the gap is

Decoupled multi-objective acquisition supplies the decision machinery. Hypervolume Knowledge Gradient values a single-objective query by the expected one-step gain in Pareto hypervolume, which is the volume of objective space dominated by the current best trade-offs. Bayesian Optimization of Multiple Objectives with Different Latencies weights knowledge-gradient gains by per-objective latency and averages over preference directions. FlexiBO divides hypervolume improvement by measured per-objective cost. All three treat cost as a fixed constant per objective and treat observations as uncensored. We reuse their acquisition structure and change the observation model and the cost model.

Censored model-based optimization supplies the motivation and a constraint. Bayesian Optimization With Censored Response Data capped algorithm-configuration runs and fit random forests by iterative imputation. It reported up to a factor-of-126 median speedup on SPEAR-SWV, but it sets caps with a heuristic slack factor. Neural Model-based Optimization with Right-Censored Observations replaced imputation with a Tobit loss, which assumes Gaussian noise in log-runtime. It found SAT configurations over 80x faster than defaults, and it showed that dropping censored points or setting them equal to the cutoff hurts predictive accuracy. That last result constrains our design: censored runs must enter the model as lower bounds. Both papers are single-objective, and neither chooses caps by value of information.

Cost-aware Stopping for Bayesian Optimization grounds cost-aware decisions in a Gittins-index analysis. Its costs are known or predictable and its runs complete, so our cap decision is a per-run analogue of its global stopping question.

Preference Models assume Proportional Hazards of Utilities shows that the Cox partial likelihood is the same mathematical object as a Plackett-Luce ranking likelihood. The point we take from it is that a proportional hazards model learns from the ordering of event times. Ordering is exactly what Pareto dominance needs, and ordering survives censoring. The same paper also warns that the model presumes survival curves that do not cross. We test that assumption directly rather than assume it.

Core mechanism

For the slow objective, let $T(x)$ be the training time design $x$ needs to reach a target validation error. We model its hazard, meaning the instantaneous chance of reaching the target at time $t$ given it has not been reached yet, as

$$h(t \mid x) = h_0(t)\, \exp(g(x)),$$

where $h_0(t)$ is a baseline hazard left completely unspecified and shared across designs, and $g(x)$ is a log relative risk with a Gaussian process prior. We fit $g$ by a Laplace approximation to the Cox partial likelihood and recover $h_0$ with the Breslow estimator.

The nonparametric baseline is where proportional hazards should matter. Training curves have warm-up phases, plateaus and sudden drops. A log-normal tail, which is what Tobit assumes, can misplace probability mass near the cap, and the cap decision depends on exactly that mass. From the fitted model we obtain the survival curve $S(t \mid x)$. The expected cost of a run on design $x$ capped at $c$ is then the restricted mean survival time plus a fixed overhead $\kappa$:

$$\text{Cost}(x, c) = \kappa + \int_0^{c} S(t \mid x)\, dt.$$

The acquisition maximizes, over the design $x$, the objective $m$ and, when $m$ is the time-to-event objective, the cap $c$, the ratio of expected one-step hypervolume gain to expected cost:

$$\alpha(x, m, c) = \frac{\mathbb{E}\left[\Delta \mathrm{HV} \mid \text{observe } \min(T_m(x), c) \text{ and whether the event occurred}\right]}{\text{Cost}_m(x, c)}.$$

The expectation is taken over fantasy outcomes. These are drawn by sampling $T$ from the posterior survival curve and then applying a Laplace-approximate update of $g$. Cheap objectives keep their usual Gaussian process surrogate and fixed cost, as in hypervolume knowledge gradient.

A secondary component reuses the same model while a run is in progress. A run still going at time $t$ has conditional survival $S(\cdot \mid x)/S(t \mid x)$. A periodic check compares the value of continuing to the cap against stopping now and spending the remaining budget on the best alternative query. This is the per-run decision that cost-aware stopping makes for the whole search.

Research Program

The program has three parts. First, we build the Gaussian-process Cox surrogate and validate its calibration under censoring on its own. Second, we plug it into a hypervolume knowledge gradient implementation with the extra cap dimension, optimizing the cap over a small grid to keep cost down. Third, we add the mid-run stop-or-continue check.

Along the way we measure where the assumptions break. We check the non-crossing condition from Nagpal's analysis by comparing Kaplan-Meier curves across design clusters. When it fails, we test a stratified variant that keeps a separate baseline hazard per architecture family. We also report the acquisition's own compute overhead as a cost, because the field's known weakness is that lookahead can cost more than the cheap objectives it schedules.

Baselines

The naive reference point is coupled multi-objective search with a global timeout. Every candidate gets all objectives measured, and runs past the timeout are recorded at the cutoff. It runs on the same benchmarks, with the same total wall-clock budget, the same initial design and the same random seeds. Beating it should be easy. If we cannot, the whole premise is wrong.

The strongest existing competitor for the full system is decoupled hypervolume knowledge gradient with a Tobit-likelihood surrogate for the time objective and a fixed cap. This is the obvious combination of Hypervolume Knowledge Gradient with the censored loss of Neural Model-based Optimization with Right-Censored Observations. For this exact pairing we found no reported result on Lacuna, so we implement it ourselves. It shares our acquisition optimizer, fantasy count and hyperparameter-tuning budget, and its fixed cap is tuned per benchmark on held-out seeds, which is generous to it. A variant that sets caps with the slack heuristic of Bayesian Optimization With Censored Response Data covers the established adaptive-capping practice.

The strongest published decoupled numbers come from FlexiBO, which reports 4.8% to 12.4% lower hypervolume error than prior methods at equal budget across seven deep-network benchmarks. We run FlexiBO and C-MOKG (Bayesian Optimization of Multiple Objectives with Different Latencies) with timeout-at-cutoff imputation. For hypervolume knowledge gradient on our benchmarks we found no reported result on Lacuna.

Beating the field means two things on at least two of the three benchmark families. The first is lower hypervolume regret at matched cumulative wall-clock cost, with confidence intervals over at least twenty seeds that separate from the tuned Tobit-plus-fixed-cap baseline. The second is that this advantage holds when acquisition overhead is counted in the cost.

Two ablations isolate the key ingredients. The first keeps our surrogate but fixes the cap; it isolates cap selection. The second keeps cap selection but swaps the Cox surrogate for Tobit, and then for a parametric Weibull proportional hazards model; it isolates the nonparametric baseline.

Why not just…?

Why not just plug a Tobit surrogate into hypervolume knowledge gradient? This is the real threat. If the log-normal assumption fits training-time curves well, Tobit with optimized caps could match us. The cap-selection ablation settles it. If Tobit-with-cap-selection equals our method, the contribution is the cap-aware acquisition, not proportional hazards, and we will report it that way. Our hypothesis is that Tobit's tail is miscalibrated near the cap on real learning curves. We test this directly by comparing predicted against empirical restricted mean survival time on held-out runs.

Why not just treat the cap as a fidelity in multi-fidelity hypervolume knowledge gradient? Multi-fidelity methods model a short run as a noisy approximation of the full value. For a time-to-target objective, a capped run is not an approximation. It is an exact lower bound, or an exact event time if the target was reached. Modeling it as a correlated fidelity throws away that structure. We include a multi-fidelity variant, with fidelity equal to the training budget, as an additional comparison, so the experiment answers this question rather than our argument.

Why not just use FlexiBO-style hypervolume improvement per unit cost with measured average costs? That approach prices a query of the slow objective at its average cost and cannot express that a short cap is cheap and still informative. Hypervolume Knowledge Gradient reports that greedy improvement-based rules undervalue pure-information queries in decoupled settings. Cost-aware stopping found naive cost-weighting unstable on LCBench and NATS-Bench. The FlexiBO baseline above tests whether these failures carry over here.

Proposed Experiments

The main testbed is LCBench, whose 35 tabular datasets record per-epoch validation error and runtime. We define time-to-target as the first wall-clock time validation error crosses a dataset-specific target, censored at the full training horizon. We pair it with parameter count as a cheap second objective.

The second testbed is NATS-Bench. It has 15,625 topologies and 32,768 size configurations, and it reports accuracy, FLOPs and latency. Here latency and FLOPs are the cheap objectives and time-to-target accuracy is the expensive one, derived from the benchmark's training records where it exposes them. Its reported ceilings, about 94.4% on CIFAR-10 and 47.3% on ImageNet-16-120, anchor the choice of target. The pipelines in CostAwareStoppingBayesOpt give us existing cost-aware evaluation harnesses for both benchmarks.

The third testbed is the two synthetic bi-objective families from C-MOKG, with 100 instances each and a cost ratio of 1 to 10. We modify them so the expensive objective is generated from known hazards. One generator follows proportional hazards. The other deliberately has crossing survival curves, so we can see the method fail in a controlled way.

As a surrogate-only check, we fit the Cox, Tobit and random-forest imputation models on censored CPLEX and SPEAR runtimes from the algorithm-configuration benchmarks. We report concordance and calibration of restricted mean survival time.

The decisive checks are three. First, hypervolume regret against cumulative wall-clock cost, overhead included, compared with every baseline. Second, the two ablations, which say whether any gain comes from cap selection, from the nonparametric baseline, or from both. Third, the crossing-hazards synthetic family, where the method should lose its advantage. If it does not, the gain is coming from somewhere other than the mechanism we claim.