Regime-Aware Successive Halving: Pruning Hyperparameter Candidates Only After Their Learning Curves Settle

Cheap hyperparameter search methods train many candidate configurations for a short time, throw away the worst, and give the survivors more time. Their weak point is timing. They compare every candidate at the same fixed checkpoints, for example after 1, 3, 9 and 27 epochs, even when some candidates are still in a slow early phase that will end in a sharp improvement. Earth-observation scientists face a similar problem when they decide whether a pixel's vegetation index has really changed. Their tools fit a sequence of straight-line segments to a noisy time series and mark the points where the slope changes. We propose running such a segmenter on each candidate's validation-loss curve during the search. A candidate is ranked only after its curve has entered a stable segment, and it is ranked by extrapolating that current segment, not its whole history.

In two sentences: standard pruning compares candidates at fixed epochs and so kills "slow starters" that would have finished best. We detect, per curve and online, when a candidate's learning dynamics have changed regime, and we delay or reorder pruning decisions accordingly. This costs almost nothing, requires no library of previously completed training runs, and keeps the total compute budget fixed.

Core Claim

Successive Halving, the "train many briefly, keep the top fraction" procedure behind Hyperband and BOHB, is known to discard slow starters. The only published fix is to predict each curve's future with a Gaussian process fitted to many fully trained curves. Successive Halving with Learning Curve Prediction via Latent Kronecker Gaussian Processes showed that such a model does rescue slow starters on Criteo 1TB learning curves. Once the cost of producing its training curves is counted, however, it is not Pareto optimal against plain Successive Halving. We claim that most of the benefit comes from knowing when a curve is comparable, not from modelling the whole curve. A per-curve change-point detector can supply that timing information with no pre-collected data.

Concretely, we model each validation-loss curve as piecewise linear in log-loss versus log-step, so each segment is a local power law. A break is a change in the local exponent. We then give Successive Halving two new rules. First, a candidate whose most recent break is too recent to have a reliably estimated segment receives a bounded deferral instead of a verdict. Second, settled candidates are ranked by extrapolating their current segment to the maximum budget.

This differs from prior work in three ways. Hyperband and BOHB use fixed geometric rungs and scalar checkpoint values (BOHB). The LKGP method needs a cross-run surrogate. MF-BOCD (Active multi-fidelity Bayesian online changepoint detection) uses cheap and expensive models to detect changes in an external data stream. We do the reverse: change detection on the training curves governs how much compute each candidate gets.

Why segmentation, and which kind

Several papers motivate and supply the method. Evidence that training curves have distinct phases comes from Efficient Hyperparameter Tuning via Trajectory Invariance Principle. It found that Transformer pretraining loss has an early stage governed by the learning rate and a late stage governed by the product of learning rate and weight decay. That paper located the boundary by eye, after the fact. If phases exist, then comparing curves across a phase boundary compares unlike things.

The segmentation machinery comes from remote sensing. LandTrendr-style straight-line fitting pins the calendar year of an abrupt change, such as a solar station being built (Characterizing the Development of Photovoltaic Power Stations…) or an Arctic lake draining (Tracking lake drainage events…), while ignoring cloud noise. PELT, a penalized dynamic program with linear expected cost, finds such breaks in vegetation series (PELT/DLM vegetation study). BFAST decomposition shows that cyclic structure must be separated from trend before breaks are read (Multi-Type Forest Change Detection Using BFAST). The training analogue is loss oscillation within each epoch and scheduler events. We treat known scheduler events, such as the end of warmup or a step decay, as fixed vertices, much as a known disturbance date would be handled.

The segmentation literature also constrains the design. Its main open problem is sensitivity to the penalty weight. Replacing one tuned knob with another would be self-defeating in a hyperparameter paper. We therefore fix the penalty at a BIC form. The cost of each segment $s$ is its residual sum of squares $\mathrm{RSS}_s$ divided by $\hat\sigma^2$, plus $\log n$ per break. Here $n$ is the number of logged evaluations and $\hat\sigma^2$ is a robust noise estimate taken from the median absolute value of successive differences of the curve. The penalty then scales with each curve's own noise, and the constant is not tuned. Sensitivity to that constant is reported as an ablation, not hidden.

Research Program

We will build three pieces.

The first is an online PELT segmenter over logged validation losses in log-log coordinates. We re-solve incrementally at each evaluation, which is cheap because curves have at most a few hundred points.

The second is a settledness test. A candidate counts as settled at a rung if its current segment spans at least $m$ evaluations and adding one more break does not lower the penalized cost. We fix $m=3$, the minimum needed to estimate a slope with a residual.

The third is Regime-Aware Successive Halving (RA-SH). At each rung, settled candidates are ranked by their current-segment extrapolation to the maximum budget. Unsettled candidates are carried to the next evaluation point instead of being pruned. The carried-over compute is capped at a fraction $\rho$ of the rung's budget, and the cap is paid for by promoting correspondingly fewer settled candidates. Total compute therefore exactly matches the Successive Halving schedule it replaces. We fix $\rho=0.2$ and ablate it. The same rules plug into BOHB by replacing its rung comparisons, which gives RA-BOHB.

Analysis will ask three questions. How often do slow starters, defined as the eventual winners ranked outside the kept fraction at a rung, show a detected break after that rung? Does timing alone or extrapolation alone produce the gain? Across architectures, do detected breaks line up with the early-to-late transition reported in the trajectory-invariance work?

Baselines

The naive reference point is random search trained to full budget, at the same total compute. Beside it we run patience-based early stopping, which halts a run when validation loss has not improved for $P$ evaluations, with $P$ chosen from a small grid whose cost is charged to the method.

The main competitors are Successive Halving, Hyperband and BOHB (BOHB). They get the same search space, the same sampled candidates (shared random seeds), the same halving factor and the same maximum budget. For the fairest comparison we also give Hyperband a tuned minimum budget. We sweep the minimum budget and report the best value in hindsight, which flatters the baseline, alongside the cost of performing that sweep.

The strongest existing slow-starter method is LKGP-guided Successive Halving (LKGP). Its authors report only qualitative results: plain Successive Halving "achieved it using less total compute" at every relative-regret level and reached zero regret once enough final candidates were kept. We found no reported numeric regret on Lacuna for the Criteo curve library. We will reproduce both on the same curves and count the surrogate's training curves as compute.

We also include per-curve parametric power-law extrapolation, which fits one power law to the whole observed curve and ranks by the extrapolated final loss.

Two ablations isolate the key ingredient. The first, "timing only", uses segmentation for deferrals but ranks by the current loss value. The second, "extrapolation only", ranks by current-segment extrapolation at fixed rungs with no deferrals. A random-deferral control defers the same number of candidates chosen at random, which checks that gains are not simply a softer pruning ratio.

RA-SH beats the field if its regret-versus-total-compute curve lies below Successive Halving's and below the tuned-minimum-budget Hyperband's on a majority of benchmark tasks, with non-overlapping confidence intervals over seeds. It must also beat whole-curve power-law extrapolation, or the segmentation is not earning its place.

Why not just…?

Why not just raise Hyperband's minimum budget so slow starters survive the first rung? This is the most serious threat. A larger minimum budget spends more on every candidate, including hopeless ones, and HPOBench reports that multi-fidelity advantages are budget-sensitive: black-box search "can eventually catch up" (HPOBench). RA-SH spends extra budget only on candidates whose curves are visibly in transition. We give the baseline its hindsight-best minimum budget. If that baseline matches RA-SH, we will report that the simpler fix suffices.

Why not just fit a power law to each curve and extrapolate? It is cheap and needs no stored curves, so it is a genuine competitor. A single power law fitted to a curve with an early plateau followed by acceleration averages the two regimes, and that systematically under-predicts exactly the slow starters. The "extrapolation only" ablation and the whole-curve baseline together test this directly. If the whole-curve fit matches RA-SH, the regime idea fails.

Why not just use a learning-curve predictor such as LKGP? It works on slow starters, but its authors show the cost of the curves needed to train it removes its advantage over plain Successive Halving. RA-SH needs no curves from other runs. On the Criteo library we will count both methods' compute identically, so the comparison is on the same axis where LKGP lost.

Why not just use patience-based early stopping? Patience cannot tell a long plateau before an acceleration from a dead run. The slow-starter failure that the LKGP paper documents for greedy stopping applies here too. It remains in the study as a baseline.

Proposed Experiments

The primary testbed is the Criteo 1TB library of 512 fully observed curves per architecture (Factorization Machines, Deep & Cross Network and mixture of experts) from the LKGP paper, if the authors release it. That is where the slow-starter failure and the compute-tax result were established. Search is simulated by revealing curves prefix by prefix, and the metric is relative regret against relative total compute.

The second testbed is JAHS-Bench-201 (JAHS-Bench-201) on CIFAR-10, Fashion-MNIST and Colorectal-Histology. Its surrogate gives per-epoch metrics up to 200 epochs over a 14-dimensional joint space that includes continuous learning rate and weight decay, where phase structure should vary most. We treat the surrogate's reported Kendall's tau of up to 0.99 as adequate fidelity but check conclusions on a subset of real runs.

The third is the NAS-Bench-201 tabular curves through HPOBench (NAS-Bench-201). Regret there is measured against the reported best accuracies of 94.37% on CIFAR-10, 73.51% on CIFAR-100 and 47.31% on ImageNet-16-120. This benchmark uses fixed training recipes, so we expect few regime differences across candidates and small gains. It serves as a negative control: RA-SH should not lose there.

Every method runs with at least 20 seeds per task under identical total compute. Compute counts the segmenter's own CPU time, which should be negligible.

Three decisive checks decide whether the idea holds. First, on the Criteo library, RA-SH must reach LKGP's regret levels at or below plain Successive Halving's compute, the Pareto position LKGP could not reach. Second, RA-SH must beat both the random-deferral control and the whole-curve power-law baseline; otherwise the gain is just softer pruning or ordinary extrapolation. Third, performance must stay within seed noise when the BIC constant is halved or doubled. If it does not, the method has only moved the tuning problem into the segmenter, the failure the segmentation literature warns about.

A cheap supplementary check reuses small-scale AdamW Transformer runs with a learning-rate by weight-decay grid. It tests whether detected breaks fall where the early-to-late transition of the trajectory-invariance work would predict. That would be the first automatic, online detection of that boundary.