PaperlayerView exact revision on arXiv

Source-linked AI summary

Tree-Structured Parzen Estimator: Understanding Its Algorithm Components and Their Roles for Better Empirical Performance

Shuhei Watanabe

arXiv:2304.11127v5cs.LGcs.AI

TL;DR

TPE is widely used, but its algorithm intuition and the roles of its control parameters have not been sufficiently discussed. This paper uses ablation studies on diverse benchmark datasets to identify those roles and recommend settings. The recommended setting improves TPE’s performance, although it is not uniformly best across all evaluated tasks and spaces.

  • Problem

    Although TPE is widely used in parameter-tuning frameworks, its algorithm intuition and control-parameter roles have not been discussed sufficiently.

  • Method

    The paper performs ablation studies of TPE control parameters and bandwidth selection across diverse benchmark datasets.

  • Results

    The recommended setting outperforms Optuna v4.0.0 except for some HPOBench and HPOlib tasks.

  • Takeaways & Limitations

    The study provides a recommended TPE setting and reports that multivariate kernels are generally recommended, while parameter effects vary across benchmark types and dimensions.

  • Takeaways & Limitations

    The implementation is not a silver bullet: it remains comparable to Optuna TPE on discrete spaces, while HEBO consistently outperforms it in the discussed comparison.

Abstract

from arXiv · show

Recent scientific advances require complex experiment design, necessitating the meticulous tuning of many experiment parameters. Tree-structured Parzen estimator (TPE) is a widely used Bayesian optimization method in recent parameter tuning frameworks such as Hyperopt and Optuna. Despite its popularity, the roles of each control parameter in TPE and the algorithm intuition have not been discussed so far. The goal of this paper is to identify the roles of each control parameter and their impacts on parameter tuning based on the ablation studies using diverse benchmark datasets. The recommended setting concluded from the ablation studies is demonstrated to improve the performance of TPE. Our TPE implementation used in this paper is available at https://github.com/nabenabe0928/tpe/tree/single-opt. OptunaHub now provides our standalone TPE implementation at https://hub.optuna.org/samplers/tpe_tutorial/.

1. Introduction

The paper addresses the limited discussion of TPE’s algorithm intuition and control-parameter roles by presenting empirical analyses across diverse benchmarks. It recommends settings from ablations and compares them with recent baselines, while restricting the main study to single-objective optimization.

  • TPE is widely used in Bayesian-optimization frameworks including Hyperopt and Optuna, with applications spanning diverse parameter-tuning settings.
  • The paper describes TPE’s algorithm intuition and empirically examines the roles of each control parameter.
  • The ablation study investigates original-TPE control parameters, bandwidth-selection enhancements, and comparisons with recent baseline methods on diverse benchmark datasets.
  • The main study narrows its scope to single-objective optimization, while extensions and applications are deferred to appendices.

2. Background

TPE is a Bayesian-optimization method that models observations by separating better and worse outcomes, fitting KDEs, and selecting configurations through a density-ratio acquisition function. Its iterative routine repeatedly updates these components, samples candidates from the better-group KDE, and evaluates the selected configuration.

  • 2.3 Tree-Structured Parzen Estimator: The density ratio r(x|D) := p(x|D(l))/p(x|D(g)) serves as TPE’s acquisition function for judging the promise of a hyperparameter configuration.
  • 2.3 Tree-Structured Parzen Estimator: The method uses kernels with bandwidths b(l) and b(g), observation weights, and an optional non-informative prior in its KDE construction.
  • 2.2 Bayesian Optimization: Bayesian optimization minimizes an objective by iteratively using an acquisition function to balance exploitation near promising observations with exploration of unseen regions.
  • 2.3 Tree-Structured Parzen Estimator: TPE models p(y|x, D) with KDE-based densities for better and worse observation groups defined by a top quantile γ.
  • 2.3 Tree-Structured Parzen Estimator: The paper tests TPE only on non-tree-structured spaces, despite TPE’s ability to handle conditional parameters in tree-structured search spaces.
  • 2.3 Tree-Structured Parzen Estimator: TPE’s main loop computes γ, splits observations, selects bandwidths, builds the two KDEs, samples candidates from p(x|D(l)), and evaluates the chosen configuration.

3. Algorithm Details of Tree-Structured Parzen Estimator

This section explains how TPE’s control parameters regulate exploration–exploitation behavior through splitting, weighting, and kernel bandwidth choices. It also shows how multivariate kernels capture parameter interactions and how bandwidth modification accounts for noisy objectives.

  • Splitting Algorithm (gamma): Smaller β1 and β2 promote exploration by enabling faster switching from the better-group mode and strengthening the prior effect.A narrower p(x|D(l)) mode is canceled more quickly by p(x|D(g)), while fewer better-group observations increase prior influence.
  • Splitting Algorithm (gamma): When objectives are multimodal, multimodality in p(x|D(l)) can explore all modes, so larger β1 or β2 does not necessarily degrade performance.This behavior is cited as explaining the use of linear splitting in multi-objective settings.
  • Weighting Algorithm: Old decay reduces the weights of older observations while assigning uniform weights to the latest 25 observations, emphasizing the current region of interest.The weighting comparison uses N(g) = 100, and the paper notes that old decay makes the acquisition function more strictly expected improvement.
  • Univariate Kernel vs Multivariate Kernel: Multivariate kernels capture interaction effects, whereas univariate kernels can assign high density away from observations and search axes separately.On the Sphere function, the multivariate kernel recognizes the exact mode location while the univariate kernel searches near x1 = 0 and x2 = 0.
  • Bandwidth Modification (consider_magic_clip): Bandwidth bmin controls precision: smaller values are more exploitative, whereas larger values are more explorative, especially when objective noise is substantial.The paper recommends relating bmin inversely to each parameter’s intrinsic cardinality; magic clipping mostly expands bandwidth.

4. Experiments

The ablation studies show that TPE control parameters affect exploration–exploitation differently across benchmark functions and HPO tasks. The recommended settings generally outperform Optuna v4.0.0, with task- and search-space-dependent bandwidth choices.

  • Kernel choice: The multivariate kernel generally outperforms the univariate kernel, except on the 10- and 30-dimensional Xin-She-Yang function.Its importance increases with evaluations in low-dimensional problems, and the paper recommends using it despite limited necessity for HPOBench.
  • Control-parameter effects: Magic clipping has a negative impact on benchmark functions but a positive impact on HPO benchmarks.The recommendation is consider_magic_clip=False for benchmark functions and True for HPO benchmarks.
  • Control-parameter effects: EI is effective for top-5% performance, while the weighting algorithm is less important for attaining top-50% performance.Old-decay and old-drop are frequent choices on HPO benchmarks but dropping past observations can limit top-5% performance.
  • The recommended setting allows TPE to outperform Optuna v4.0.0 except for some tasks of HPOBench and HPOlib.
  • Bandwidth selection: Bandwidth-selection heuristics vary by task: scott is best for benchmark functions, optuna for HPOBench and HPOlib, and hyperopt for JAHS-Bench-201.Hyperopt is recommended by default because it shows the most stable performance across settings.

5. Conclusion

The paper explains TPE components and control-parameter choices, emphasizing noise-aware settings for bandwidth selection. It recommends defaults and reports comparisons across diverse problems.

  • TPE control-parameter settings should change with the noise level of objective functions.Bandwidth selection is especially sensitive to noise because of intrinsic cardinality.
  • The paper provides a recommended default setting despite task-dependent control-parameter behavior.
  • The recommended TPE version is compared with various baseline methods on diverse problems.

Appendix A. The Derivation of the Acquisition Function

The appendix relates PI and EI under an assumption, derives the acquisition-function transformation, and situates TPE among extensions and related classifier-based methods. It also notes the paper’s single-objective scope and summarizes limited available theory for TPE.

  • Acquisition-function derivation: PI and EI are equivalent under the assumption in Eq. (4), so the appendix discusses PI for simplicity.The derivation plugs Eq. (4) into the PI formulation in Eq. (3) and obtains Eq. (6).
  • Extensions: The paper focuses on single-objective TPE, while MOTPE and c-TPE provide strict generalizations for multi-objective and constrained optimization.These generalizations coincide with original TPE when the number of objectives is 1 or the violation probability is almost everywhere zero, respectively.
  • Extensions: TPE has also been adapted to multi-fidelity, meta-learning, combinatorial, and categorical-parameter optimization settings.The cited adaptations combine TPE with Hyperband, use task similarity, or introduce a categorical kernel.
  • Theory and related methods: TPE has fewer theoretical results than BORE because KDE is multimodal and TPE explicitly handles density ratios.The cited theory shows D(l) asymptotically converges to configurations in a γ′-quantile set under a noiseless objective, ϵ-greedy selection, and fixed γ.

C.2 group Parameter in Optuna

The group parameter partitions a tree-structured search space into observation-defined subspaces and optimizes the acquisition function separately within each subspace. Conditional dimensions are represented through binary activation functions, so parameter dependencies determine which subspaces occur.

  • Tree-structured search space: A tree-structured search space consists of dimensions whose conditional parameters are activated by binary functions over the other dimensions.The example uses layer count and optimizer choices to determine whether dropout, coefficients, or momentum parameters are defined.
  • Tree-structured search space: In the example, nested optimizer parameters require their parent choices to be defined, producing binary activation functions such as c7 = c8 = I[x1 ≥2]I[x6 = adam].The dependencies make x7, x8, and x9 conditional on x6, while x6 is conditional on x1.
  • Group parameter: The group parameter enumerates subspaces Xs from observed missing-value patterns and optimizes the acquisition function separately in each subspace.For the example, it produces several combinations of layer, optimizer, coefficient, and momentum dimensions.
  • KDE bandwidth: Bandwidths are selected independently for each dimension from sorted observations, optionally including the midpoint prior.The prior is represented by adding x = (L + R)/2 to the observations.

C.3.1 Hyperopt Implementation

The Hyperopt implementation can augment observations with the domain endpoints before computing KDE bandwidths. Its bandwidth heuristic responds to local observation density by widening kernels in sparse regions and narrowing them in dense regions.

  • Endpoint handling: When consider_endpoints=True, the implementation adds the lower and upper domain bounds as observations; otherwise, it uses only the original observations.The augmented set contains x0 = L and xN+1 = R.
  • Bandwidth computation: The bandwidth bn is computed for each kernel centered at observation xn.The method defines k(·, xn|bn) for n = 1, 2, . . . , N.
  • Bandwidth heuristic: Bandwidths are wider in sparse regions and narrower in dense regions, adapting KDE smoothing to observation concentration.This is the stated effect of the heuristic on local kernel widths.

C.3.2 BOHB Implementation (Scott’s Rule)

BOHB computes bandwidth using Scott’s rule for univariate Gaussian kernels, with separate treatment for dimensions and categorical parameters. The benchmark functions span arbitrary dimensions, with experiments using 5, 10, or 30 dimensions.

  • Scott’s rule calculates bandwidth for the univariate Gaussian kernel.
  • The benchmark functions support arbitrary dimension D, with experiments using D ∈ {5, 10, 30}.
  • BOHB calculates bandwidth separately for each dimension and treats categorical parameters as numerical parameters.

C.3.3 Optuna v4.0.0 Implementation

Optuna v4.0.0 computes bandwidth from the search-space dimension and observation count, while categorical bandwidth uses an Aitchison-Aitken kernel. Unlike the other methods, its numerical bandwidth does not depend on the observed values or target range.

  • Optuna v4.0.0 computes bandwidth using the search-space dimension D and observation count N.The target parameter is defined on [L, R].
  • Unlike the other methods, Optuna’s bandwidth depends only on the observation count and search-space dimension.
  • For a categorical parameter with C categories, Optuna v4.0.0 uses an Aitchison-Aitken kernel.

Appendix D. The Details of Benchmarks

The appendix evaluates TPE across benchmark functions, tabular HPO benchmarks, and surrogate benchmarks with varied dimensionalities and parameter types. It also describes probability-mass visualization and PED-ANOVA analyses for studying task behavior and hyperparameter importance.

  • HPO benchmarks: HPOBench and HPOlib are tabular benchmarks, whereas JAHS-Bench-201 is a surrogate benchmark.HPOBench covers 8 OpenML datasets, HPOlib covers 4 datasets, and JAHS-Bench-201 covers CIFAR10, Fashion MNIST, and colorectal histology.
  • Benchmark types: Tabular benchmarks query pre-recorded performance values and cannot handle continuous parameters.
  • Benchmark types: Surrogate benchmarks return predicted performance values from a surrogate model for the corresponding hyperparameter configurations.
  • Visualization methodology: Probability-mass visualizations use a top-performance quantile, one-dimensional KDEs, their mean across tasks, and the resulting mean probability mass function.The specified quantiles are α = 0.05 and 0.5.
  • Hyperparameter importance: PED-ANOVA measures global importance for achieving top-50% performance and local importance for achieving top-5% performance from the top-50% set.

Appendix E. Additional Results

The appendix compares ablations, bandwidth-selection analyses, and baseline methods across benchmark functions and HPO benchmarks. Results are visualized with cumulative-minimum curves and violin-plot-like distributions across evaluations and settings.

  • Visualization methodology: The visualizations plot cumulative minimum performance curves and gathered-result distributions at 50, 100, 150, and 200 evaluations.Violin-plot-like distributions replace standard errors to retain distributional information, and Optuna v4.0.0 is included as a baseline.
  • Ablation study: Figures 18–23 present ablation-study results on benchmark functions and HPO benchmarks.
  • Bandwidth selection: Figures 24–39 present bandwidth-selection analyses on benchmark functions and HPO benchmarks.
  • Baseline comparisons: Figures 40–44 compare the method with baseline methods on benchmark functions and HPO benchmarks.

Appendix F. General Advice for Hyperparameter Optimization

The appendix recommends designing compact, well-initialized search spaces, selecting algorithms suited to parameter types, and restarting optimization when non-global methods become trapped. Its ablation figures compare cumulative minimum objectives across evaluations and benchmark settings.

  • Search-space design: Use ordinal parameters instead of continuous parameters when the search space permits discrete ordered choices.The appendix illustrates this by replacing a continuous dropout parameter with choices generated from an intrinsic cardinality.
  • Search-space design: Reduce or bundle hyperparameters to mitigate the curse of dimensionality, especially for neural-network configurations.The paper gives bundling each layer’s dropout rate and activation functions as an example.
  • Search-space design: Include strong baseline settings in initial configurations to warm-start the optimization.This recommendation is presented as the second search-space design point.
  • Algorithm selection: For numerical-only spaces, consider CMA-ES for large budgets or Nelder-Mead for small budgets; categorical or conditional spaces favor random search or Bayesian optimization.The paper also characterizes TPE as a promising local-search option for categorical or conditional spaces.
  • Restarting optimization: Restart optimization after a certain number of evaluations because non-global methods such as TPE and Nelder-Mead can get stuck in local optima.The appendix identifies restarting as especially important for these methods because promising regions may be missed.
  • Ablation-study readout: The ablation figures plot evaluation count against cumulative minimum objective, with solid lines showing means across control-parameter configurations and transparent shades showing distributions.The figures use distributions at 50, 100, 150, and 200 evaluations and provide Optuna v4.0.0 as a baseline in the described plots.
Loading 2304.11127v5…