Best Arm Identification with Retroactively Increased Sampling Budget for More Resource-Efficient HPO

Jasmin Brandt, Marcel Wever, Viktor Bengs, Eyke Hüllermeier

Hyperparameter Optimization (HPO) is a critical yet computationally expensive phase in machine learning workflows. Among the most popular strategies is Successive Halving (SHA), which efficiently identifies high-performing configurations by discarding poor performers early. However, SHA typically requires a fixed maximum budget ($R$) to be defined upfront. If a researcher later determines that a larger budget is necessary to distinguish between top candidates, standard SHA necessitates a complete restart, discarding all previous computations.

Presented at IJCAI-24, this paper introduces incremental Successive Halving (iSHA), a synchronous HPO algorithm designed to handle retroactively increased budgets without sacrificing theoretical guarantees or computational efficiency.

The iSHA Method

iSHA is a "stateful" variant of SHA that treats previous evaluations as valuable assets rather than sunk costs. When the maximum budget is increased, iSHA follows a structured three-step process to expand the search space while preserving existing knowledge:

  1. Padding: The algorithm adds new hyperparameter configurations to the initial evaluation pool to ensure the density of the search space matches what would be required for a larger, single-run SHA experiment.
  2. Selective Execution: It evaluates only these new configurations on the lower budget levels (rungs).
  3. Smart Promotion: These new results are merged with the already-promoted configurations from the previous run.
The incremental Successive Halving (iSHA) process, showing how previous configurations are padded and promoted to higher budgets.

By maintaining a synchronous, batch-style structure, iSHA ensures that promotion decisions are made with full information about the current candidate pool, avoiding the "consistency gap" often found in asynchronous methods.

Experimental Evaluation

The authors evaluated iSHA using the YAHPO-Gym surrogate benchmark suite, covering a wide range of models including neural networks (lcbench, nb301), SVMs, Random Forests, and XGBoost. The "budget" or fidelity was defined either as training epochs or fractions of the training dataset.

Key Results and Resource Efficiency

The primary advantage of iSHA is its ability to achieve the same mathematical results as a from-scratch SHA run while significantly reducing the marginal cost of increasing the budget.

  • Budget Savings: iSHA reduced the consumed budget by approximately 75% (at a reduction factor $\eta=2$) and 84.5% (at $\eta=3$) compared to the cost of re-running SHA from scratch.
  • Consistency and Reliability: Unlike asynchronous methods like ASHA or PASHA, which may accidentally discard "late-blooming" configurations due to premature promotions, iSHA maintains a consistency metric of over 95% with standard SHA.
Performance difference vs. relative saved budget. iSHA (green) maintains high performance consistency (near zero difference) while saving significant resources.

As shown in the performance comparisons, while algorithms like PASHA can sometimes save more budget, they often suffer from significant performance degradation. iSHA (represented in green) consistently clusters near the zero-performance-difference line, indicating it reliably finds the same "best arm" as a full-budget run.

Theoretical Contributions

Beyond its practical utility, the paper establishes a new theoretical lower bound for the "Best Arm Identification" problem in non-stochastic settings. The authors prove that iSHA is nearly optimal in its budget expenditure and identifies an $\epsilon$-optimal configuration with the same probability as standard SHA, despite its incremental nature.

Conclusion and Future Work

iSHA provides a robust solution for practitioners with limited hardware—such as those training on a single GPU—who need the flexibility to scale their experiments dynamically. Future work aims to integrate this incremental logic into broader frameworks like Hyperband to create an "incremental Hyperband" (iHB) capable of managing multiple trade-offs between search breadth and depth.

Summary updated

BibTeX
@inproceedings{brandt2024best,
  author = {Jasmin Brandt and Marcel Wever and Viktor Bengs and Eyke Hüllermeier},
  title = {{Best Arm Identification with Retroactively Increased Sampling Budget for More Resource-Efficient HPO}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure