Abstract
Multi-fidelity Hyperparameter Optimization (HPO) algorithms, such as Successive Halving (SHA), typically require a pre-defined maximum evaluation budget. This constraint forces a trade-off: setting the budget too low risks suboptimal results, while setting it too high wastes resources. If a researcher decides to increase the budget post-hoc, standard methods require a full restart, leading to significant computational waste. We present incremental Successive Halving (iSHA), a novel approach that enables retroactive budget increases by maintaining state and padding previous runs with new configurations. Our results across diverse benchmarks show that iSHA saves up to 85% of computational costs compared to full restarts while maintaining near-perfect consistency with standard SHA.
Introduction
In machine learning, Hyperparameter Optimization (HPO) is critical for model performance. The Successive Halving Algorithm (SHA) has emerged as a standard for efficient HPO by allocating more resources to promising configurations. However, SHA's reliance on a fixed maximum budget ($R$) is a significant limitation. In practice, researchers often discover that their initial budget was insufficient only after the algorithm has finished.
Existing asynchronous variants like ASHA attempt to solve related problems but often lack theoretical robustness or consistency with the original SHA results. This paper introduces iSHA to address the "sunk cost" problem in HPO, allowing for seamless scaling of the sampling budget without discarding previous work.
Incremental Successive Halving (iSHA)
The core innovation of iSHA is its "stateful" nature. Unlike standard SHA, which is stateless and must be re-run if parameters change, iSHA retains the results of previous evaluations. When the maximum budget is increased, iSHA performs a "synchronous padding" step. It calculates the number of configurations required for the new budget level and adds new configurations to the initial pool.
As shown in Figure 1, the algorithm promotes configurations through "rungs" (budget levels). It only executes new configurations on lower rungs, comparing their performance against stored results from the previous run. This ensures that the final selection is based on the same competitive criteria as a fresh SHA run, but with a fraction of the computation. Crucially, the authors establish a theoretical lower bound for the budget required to identify a near-optimal configuration, demonstrating that iSHA's efficiency is near-optimal.
Experimental Evaluation
We evaluated iSHA using the YAHPO-Gym surrogate benchmark suite. This allowed for extensive testing across various model types and datasets, including neural networks (lcbench), SVMs, Random Forests, and XGBoost (rbv2 benchmarks), as well as neural architecture search (nb301). These benchmarks cover different fidelity types, such as training epochs and dataset fractions.
Key Results and Discussion
Our experiments focused on two primary metrics: resource efficiency and consistency.
Resource Efficiency
iSHA demonstrates remarkable efficiency. When the reduction factor ($\eta$) is set to 2, iSHA saves approximately 75% of the budget compared to a full restart. With $\eta=3$, the savings increase to 84.5%. This allows researchers to "start small" and only invest more resources if the initial results are promising, without any penalty for the phased approach.
Consistency and Performance
A critical requirement for any incremental method is that it should not sacrifice quality. We compared iSHA against ASHA and PASHA.
As illustrated in Figure 2, iSHA (green) consistently achieves a performance difference near zero relative to a full SHA re-run. In contrast, asynchronous methods like ASHA (blue) and PASHA (orange) show higher variance and often fail to identify the same "best" configuration. On a scale where 1.0 represents perfect alignment with a full SHA re-run, iSHA consistently scored above 0.95, whereas ASHA and PASHA ranged between 0.56 and 0.77.
Conclusion
Incremental Successive Halving (iSHA) provides a robust solution to the fixed-budget limitation of standard HPO algorithms. By enabling retroactive budget increases with minimal overhead, iSHA promotes more sustainable and flexible machine learning research. This "Green HPO" approach effectively eliminates the sunk cost of computation, reducing the environmental impact of large-scale model tuning. Future work will explore integrating iSHA with advanced sampling strategies like Bayesian Optimization to further enhance its efficiency in high-dimensional search spaces.
Summary updated