ECONOMIC HYPERPARAMETER OPTIMIZATION WITH BLENDED SEARCH STRATEGY

Chi Wang, Qingyun Wu, Silu Huang, Amin SaiedICLR 2021 · OpenReview

TL;DR

BlendSearch is a new hyperparameter optimization (HPO) strategy that combines the wide-reaching exploration of global search with the cost-conscious precision of local search. By dynamically prioritizing search threads based on their efficiency, it finds high-quality models while consuming significantly fewer computational resources—in one real-world NLP task, it used just 3% of the resources required by state-of-the-art competitors.

What Problem Does This Paper Address?

Hyperparameter optimization is the "black art" of tuning machine learning models (e.g., setting learning rates or tree depths) to achieve peak performance. For modern deep learning, this process is notoriously expensive, often requiring hundreds of "trials" that can take hours or days each.

The authors identify a major gap in current HPO methods: cost heterogeneity. In many search spaces, some configurations are much more expensive to evaluate than others (e.g., training a forest with 1,000 trees vs. 10 trees).

  • Global Search (like Bayesian Optimization) is great at finding the best overall settings but often wastes the budget on expensive, mediocre configurations early on.
  • Local Search is cost-effective and stays in "cheap" neighborhoods but frequently gets trapped in local optima.
  • Multi-fidelity methods (like ASHA) help by pruning bad trials early, but they require specific "proxies" (like training for fewer epochs) that aren't always available or reliable.

Methods

The authors introduce BlendSearch, a framework that manages a "pool" of search threads. It starts with one global search thread and gradually adds local search threads as promising areas are discovered.

BlendSearch Framework

Key innovations include:

  1. Search Thread Selector: Instead of running one algorithm, BlendSearch uses a priority metric to decide which thread to run next. This metric estimates the "improvement speed"—how much the loss is likely to drop per dollar (or second) spent—using linear extrapolation of past results.
  2. Config Validator (The Guardrail): When the global search suggests a new point, a validator checks if it falls within an "admissible region." This region starts small (focused on low-cost areas) and expands over time. If a global suggestion is too "expensive" or risky, the system falls back to a local search thread instead.
  3. Thread Synergy: Global search is used to "seed" new local search threads. If a global trial performs better than average, a new local thread is born at that location to refine the results.

Datasets

The researchers evaluated BlendSearch across a diverse set of challenges:

  • AutoML Benchmark: 37 tabular datasets representing real-world classification problems of varying sizes and difficulties.
  • Tree-based Models: Extensive tuning of XGBoost and LightGBM hyperparameters.
  • Deep Learning: Tuning DeepTables (a toolkit for deep learning on tabular data).
  • Production NLP Task: Fine-tuning a Turing-NLRv2 transformer model (340 million parameters) on a sequence classification task with 52,000 labeled examples.

Key Insights and Ideas

  • Cost as a First-Class Citizen: Most HPO algorithms treat every trial as having equal cost. BlendSearch recognizes that time is money and explicitly prioritizes "bang for the buck."
  • The Power of "Admissible Regions": By preventing the global search from jumping into high-cost configurations too early, the algorithm naturally explores the "cheap" parts of the search space first, effectively "democratizing" HPO for users with limited hardware.
  • Dynamic Resource Allocation: The priority metric allows the system to kill off stagnant local searches and double down on threads that are rapidly improving, mimicking how a human data scientist might manually monitor experiments.

Key Results

The empirical results show that BlendSearch consistently finds better models faster than Bayesian Optimization (BO), Local Search (LS), or BOwLS.

Scaled Loss Over Time
  • Efficiency in NLP: In the transformer fine-tuning task, BlendSearch achieved a higher F1 score (0.652) in just 12 GPU-hours on a single VM. In comparison, ASHA-16 (a popular multi-fidelity method) required 384 GPU-hours across 16 VMs to reach a lower F1 score (0.640).
  • Robustness: On the AutoML benchmark, BlendSearch's "aggregated rank" was consistently lower (better) than competitors across both short (1h) and long (4h) time budgets.
  • Agnostic to Initialization: Even when the authors didn't provide a "low-cost" starting point, BlendSearch's internal logic allowed it to outperform standard BO by effectively managing the search trajectory.

Limitations and Future Work

While BlendSearch is highly effective, the authors note a few areas for growth:

  • Controlled Dimensions: The algorithm performs best when the user can identify which hyperparameters correlate with cost (e.g., "number of trees"). Without this knowledge, the "admissible region" logic is less impactful.
  • Theory vs. Practice: The paper is heavily empirical. The authors mention that formal theoretical guarantees regarding convergence rates and total resource consumption are still needed.
  • Parallelization: While the framework naturally supports parallel trials (and is supported in their open-source library, FLAML), the core logic in this paper focuses on the sequential efficiency of the search strategy.

Summary updated

Abstract

We study the problem of using low cost to search for hyperparameter configurations in a large search space with heterogeneous evaluation cost and model quality. We propose a blended search strategy to combine the strengths of global and local search, and prioritize them on the fly with the goal of minimizing the total cost spent in finding good configurations. Our approach demonstrates robust performance for tuning both tree-based models and deep neural networks on a large AutoML benchmark, as well as superior performance in model quality, time, and resource consumption for a production transformer-based NLP model fine-tuning task.
BibTeX
@inproceedings{wang2021economic,
  author = {Chi Wang and Qingyun Wu and Silu Huang and Amin Saied},
  title = {{ECONOMIC HYPERPARAMETER OPTIMIZATION WITH BLENDED SEARCH STRATEGY}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=VbLH04pRA3},
}
Figure