Frugal Optimization for Cost-related Hyperparameters

Qingyun Wu, Chi Wang, Silu HuangAAAI 2021 · DOI

Introduction

Hyperparameter optimization (HPO) is essential for maximizing machine learning model performance. Traditionally, HPO is framed as a "black-box" problem where the primary goal is to minimize the number of trials. However, this approach overlooks a critical reality: not all trials cost the same. Training a model with minimal complexity (e.g., few trees in a forest) is significantly faster and cheaper than training a highly complex one. Standard methods often waste resources evaluating expensive configurations that offer diminishing returns.

This paper introduces CFO (Cost-Frugal Optimization), a framework designed to find optimal configurations while minimizing total computational cost (wall-clock time).

The CFO Approach

CFO is built upon a theoretical core called FLOW$^2$, a randomized direct-search method. Unlike Bayesian Optimization, which often requires complex cost models to predict evaluation times, CFO manages cost implicitly through its search strategy.

How it Works

  1. Start Cheap: The algorithm begins at a low-cost configuration (e.g., shallow trees, small learning rates).
  2. Cautious Exploration: It samples random directions in the hyperparameter space. If a small step in a direction reduces validation loss, it moves; otherwise, it stays put.
  3. Dynamic Scaling: The search radius adjusts based on progress, and randomized restarts help the algorithm escape local optima.
CFO demonstrates rapid convergence on the 'adult' dataset by starting with low-cost configurations and moving efficiently toward the optimum.

By starting at a low-cost point and moving in small increments, CFO naturally explores the most affordable regions of the search space first. It only ventures into expensive, high-complexity territory if the loss continues to drop significantly, effectively using "local monotonicity" as a guardrail against overfitting and wasted computation.

Experimental Evaluation

The researchers evaluated CFO against industry-standard baselines, including BOHB, SMAC, and TPE. The benchmarks included:

  • AutoML Benchmark: 39 large-scale classification tasks.
  • PMLB Regression Benchmark: 14 regression tasks.
  • Models: Tuning 9 hyperparameters for XGBoost and various Deep Neural Network (DNN) architectures.

Key Results and Insights

CFO demonstrated overwhelming dominance in both accuracy and efficiency:

  • Success Rate: In XGBoost benchmarks, CFO achieved the best loss on 96% of the datasets within the allocated time budget, compared to just 32% for the next best baseline.
  • Speedup: The method achieved up to three orders of magnitude speedup in reaching target loss levels compared to traditional HPO methods.
  • Anytime Performance: As shown in the wall-clock time plots, CFO's loss curves drop much earlier and faster than competitors, making it ideal for practitioners with limited time or budgets.
Across a variety of datasets (a-f), CFO (black line) consistently reaches lower loss levels faster than traditional HPO baselines.

Conclusion and Future Work

CFO proves that a simple search strategy starting from a low-cost point can outperform complex, cost-aware Bayesian models. While highly effective, the authors note that CFO's performance depends on identifying a sensible "low-cost" starting point. Future research will focus on improving the handling of high-cardinality categorical variables and increasing robustness to noisy validation scores in stochastic training environments.

Summary updated

BibTeX
@inproceedings{wu2021frugal,
  author = {Qingyun Wu and Chi Wang and Silu Huang},
  title = {{Frugal Optimization for Cost-related Hyperparameters}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i12.17239},
}
Figure