How do you keep successive halving from cutting a configuration that only wins at full budget?
answer
- one unchecked assumption underneath the race
- learning curves that cross
- ranking agreement, not score agreement
- less data changes which configuration wins
- start the race later, cut more gently
basics
~20 sSuccessive halving assumes the ranking at a small budget matches the ranking at full budget. When it does not, raise the first rung's budget, cut less aggressively, run less aggressive Hyperband brackets, and validate the proxy's rank correlation first.
solid answer
~50 sThe whole method rests on one assumption: performance at a cheap fidelity ranks configurations roughly the way full training would. Two families of configuration break it. Fast-but-plateauing settings — an aggressive learning rate, weak regularisation — look excellent after one epoch and lose later. Slow-but-strong settings — heavy regularisation, larger capacity, more trees — look mediocre early and win at the end. A 10% subsample fidelity has its own bias: it systematically favours whatever configuration suits a small dataset, so it under-rates exactly the high-capacity settings you might want. I would first measure the assumption rather than argue about it: take a pilot of a dozen or so configurations, score them at both the proxy and the full fidelity, and look at the rank correlation. If it is weak, raise the minimum rung budget, lower the cut factor, lean on the less aggressive Hyperband brackets, or promote on an extrapolated learning curve rather than the instantaneous score.
go deeper
Understand that stopping trials early can throw away a setting that would have won with more training, and that a short run is only a guess at the final result.
Explain how learning curves cross and name configuration types that start slow but finish strong. Know that a subsample proxy shifts which settings look good, rather than just adding noise.
Show a measurement plan: a pilot at both fidelities, rank correlation and top-k overlap, then concrete adjustments to rung budget, cut factor or promotion rule. Interviewers want the diagnosis, not just the vocabulary.
Decide how much budget the organisation spends validating its own proxies, and set the default fidelity policy for a model family so every team is not rediscovering the same crossing-curve failure.
## The assumption, stated plainly Every early-stopping search — successive halving, Hyperband, any home-grown "kill the bottom half after one epoch" rule — makes the same bet: **rank at low fidelity approximates rank at full fidelity**. Nothing in the algorithm checks this. If the bet is wrong, the search runs beautifully, finishes fast, and returns the wrong configuration with full confidence. ## How the bet fails **Learning curves cross.** A large learning rate drops the loss quickly and then oscillates around a worse plateau; a small one starts unimpressively and finishes better. Rank them at one epoch and you rank them backwards. The same happens between a lightly regularised model that fits the training signal fast and a heavily regularised one that needs more iterations to reach a better generalisation point. **Capacity needs budget.** A deeper tree ensemble, more boosting rounds, a wider model — these often trail early and pass later. Cutting at rung zero systematically prunes the high-capacity end of the space. **Subsample fidelity is not a neutral shrink.** If the cheap fidelity is "train on 10% of the rows", you are not approximating the full problem; you are solving a different one whose optimum sits at *more* regularisation and *less* capacity. Any configuration whose value depends on having data — deeper interactions, less shrinkage, richer feature crosses — is under-rated by construction. Fidelity by iterations distorts less than fidelity by data size, when both are available. **Noise at the first rung.** With a very small budget, the score differences between configurations may be smaller than the run-to-run noise. Then the first cut is close to random, and the aggressive bracket is spending its budget to sample the space rather than to rank it. ## Diagnosing before trusting Do this once per problem family, not once per run: 1. Sample a pilot set of maybe 12-20 configurations spanning the space. 2. Score each at the proxy fidelity and at full fidelity. 3. Compute a rank correlation (Spearman or Kendall) between the two orderings, and separately check the *top-k overlap* — whether the proxy's top third contains the full-fidelity winner, which is what successive halving actually needs. Absolute agreement of scores does not matter at all. A proxy that reads three points low everywhere but orders configurations correctly is a perfect proxy. This is the most common misunderstanding in the area. ## Fixes, in rough order of cost - **Raise the minimum rung budget.** Start the race after the point where learning curves have stopped crossing wildly. Costs budget, buys ranking validity. - **Lower the cut factor.** Cutting two-thirds per rung is aggressive; cutting half is gentler and keeps more slow starters alive at the price of fewer rungs. - **Use the less aggressive brackets.** This is precisely what Hyperband's bracket sweep buys you, and it is the principled version of the previous two fixes: you do not have to know which aggressiveness is right. - **Promote on trend, not level.** Instead of the current score, promote on a projection of where the learning curve is heading — a simple fit to the observed curve is usually enough to save a slow starter that is still improving steeply. - **Constrain the search space instead.** If you know a knob only makes sense at full budget, do not put it in the race; fix it, or tune it in a separate small full-fidelity search. - **Reserve a rescue slot.** Keep a small share of the budget for full-budget runs of a few configurations that were cut early but sat in the top of the space by other criteria. This is cheap insurance and it also gives you evidence about whether your proxy is working. ## What to report afterwards When the race ends, only the survivor has a full-budget score. It is tempting to present the rung-zero scores as a leaderboard; do not, because those numbers were produced at different budgets and mean different things. If you need a comparison between the top few, run them all at full budget. ## What interviewers listen for That you can name the assumption without prompting, that you propose *measuring* rank agreement rather than reasoning about it, and that you understand a subsample proxy is biased rather than merely noisy. A candidate who says "just increase the number of configurations" has misdiagnosed: more configurations at the same tiny first-rung budget makes the aggressive cut *more* likely to lose the winner, not less.
- Which hyperparameters does a 10% subsample proxy most systematically misjudge?Everything that trades capacity against data volume. Regularisation strength, tree depth, minimum samples per leaf, the number of boosting rounds and any feature-richness knob shift their optimum when the training set shrinks. The proxy rewards small, heavily regularised models, so it under-rates configurations that only pay off with the full dataset.
- How would you decide whether a proxy fidelity is trustworthy?Score a pilot of a dozen or more spread-out configurations at both the proxy and full fidelity, then measure rank correlation between the two orderings and check whether the proxy's top third contains the full-fidelity winner. Top-k overlap is the metric that matches what the promotion rule needs; absolute score agreement is irrelevant.
- Is more configurations at the same tiny first rung a fix?No, and it usually makes things worse. Widening the first rung without raising its budget means more configurations are ranked by an equally unreliable signal, so the probability that the eventual winner survives the first cut goes down, not up. Fix the rung budget or the cut factor instead.
saying these in an interview costs you the question
- Treats early rankings as ground truth about final performance
- Compares proxy and full scores by absolute value instead of rank
- Thinks a data subsample is an unbiased cheap version of the problem
- Adds more configurations at the same tiny starting budget
- Reports first-rung scores as a leaderboard across configurations