PaperlayerView exact revision on arXiv

Source-linked AI summary

Warm Starting CMA-ES for Hyperparameter Optimization

Masahiro Nomura, Shuhei Watanabe, Youhei Akimoto, Yoshihiko Ozaki, Masaki Onishi

arXiv:2012.06932v1cs.LG

TL;DR

With limited evaluation budgets, CMA-ES can underperform BO because its covariance adaptation takes time. WS-CMA-ES initializes CMA-ES using prior knowledge from related tasks and a task-similarity design. Experiments report faster solutions than CMA-ES on HPO tasks, with performance tied to task similarity and a risk when tasks are dissimilar.

  • Problem

    With severely limited evaluation budgets, CMA-ES may not adapt its covariance enough to outperform BO, a concern for users with limited computational resources.

    Source: §1 · p. 1, §2.2 · p. 2

  • Method

    WS-CMA-ES estimates a promising distribution on a source task and initializes the CMA-ES mean and covariance to approximate it, using a defined task similarity.

    Source: §1 · p. 1, §3.1 · p. 3

  • Results

    WS-CMA-ES and WS-only found better hyperparameter settings earlier than other methods, and WS-CMA-ES later adapted to converge to better solutions than WS-only.

    Source: Results and Discussion on Knowledge… · p. 6

  • Takeaways & Limitations

    Experiments on synthetic and HPO problems indicate that WS-CMA-ES can be effective with low budgets or when source and target tasks are not very similar.

    Source: §7 · p. 7

    WS-CMA-ES can perform worse than CMA-ES when source and target task similarity is low, and the authors identify automatic dissimilarity detection and switching back as needed for reliability.

    Source: §7 · p. 7

Abstract

from arXiv · show

Hyperparameter optimization (HPO), formulated as black-box optimization (BBO), is recognized as essential for automation and high performance of machine learning approaches. The CMA-ES is a promising BBO approach with a high degree of parallelism, and has been applied to HPO tasks, often under parallel implementation, and shown superior performance to other approaches including Bayesian optimization (BO). However, if the budget of hyperparameter evaluations is severely limited, which is often the case for end users who do not deserve parallel computing, the CMA-ES exhausts the budget without improving the performance due to its long adaptation phase, resulting in being outperformed by BO approaches. To address this issue, we propose to transfer prior knowledge on similar HPO tasks through the initialization of the CMA-ES, leading to significantly shortening the adaptation time. The knowledge transfer is designed based on the novel definition of task similarity, with which the correlation of the performance of the proposed approach is confirmed on synthetic problems. The proposed warm starting CMA-ES, called WS-CMA-ES, is applied to different HPO tasks where some prior knowledge is available, showing its superior performance over the original CMA-ES as well as BO approaches with or without using the prior knowledge.

1 Introduction

With severely limited evaluation budgets, CMA-ES may underperform Bayesian optimization because its adaptation phase is long. WS-CMA-ES uses related-task knowledge to initialize CMA-ES, and experiments report faster convergence and benefits tied to task similarity.

1 Introduction

  • CMA-ES updates a multivariate Gaussian distribution and can evaluate sampled candidates in parallel; it has shown strong BBO performance with moderate-to-large budgets.The cited benchmark context uses budgets greater than 100 times the number of variables.Source: §1 · p. 1
  • Under severely limited evaluation budgets, CMA-ES may fail to improve performance and be outperformed by BO because it needs a long adaptation phase.Source: §1 · p. 1
  • WS-CMA-ES uses source-task knowledge to shorten CMA-ES adaptation by initializing its search from the relationship between source and target tasks.The method estimates a promising distribution on the source task and initializes the CMA-ES mean and covariance by minimizing KL divergence to that distribution.Source: §1 · p. 1
  • The paper formally defines a promising distribution and task similarity to guide the design of CMA-ES warm starting.Source: §1 · p. 2
  • Experiments report that WS-CMA-ES performance correlates with the defined task similarity, and synthetic tests find it more effective than naive warm starts even when tasks are not very similar.Source: §1 · p. 2
  • WS-CMA-ES converges faster than existing HPO methods, and the study compares it with CMA-ES, GP-EI, TPE, MTBO, and MT-BOHAMIANN.Source: §1 · p. 2

2 Background

The section formulates HPO as black-box minimization and describes CMA-ES as an optimizer that adapts a multivariate Gaussian from ranked candidates. Its covariance adaptation can be too slow for limited HPO budgets, motivating parallel evaluation, restricted covariance models, or transfer of source-task observations.

2 Background

  • HPO is framed as minimizing a black-box function over a compact measurable search space, where each solution is a hyperparameter setting and its function value is generally validation error.Source: §2 · p. 2

2.1 CMA-ES

  • CMA-ES samples candidates from a multivariate Gaussian and updates its mean and covariance using candidate rankings; its rank-based and affine invariances support application across varied objectives and search spaces.Source: §2.1 · p. 2

2.2 CMA-ES for Hyperparameter Optimization

  • With limited HPO budgets, CMA-ES may not adapt its covariance enough to outperform BO; default covariance learning rates of Θ(1/d^2) imply O(d^2) iterations for adaptation.Source: §2.2 · p. 2
  • Larger populations with parallel evaluation or restricted covariance models can accelerate adaptation, but parallelism requires resources and restricted models compromise rotational invariance.Source: §2.2 · p. 2

3 Warm Starting CMA-ES

WS-CMA-ES transfers source-task observations into CMA-ES initialization to shorten adaptation, using task similarity to characterize when that transfer is promising. The section defines the distributions and similarity measure, then describes how source observations determine the initial search distribution.

3 Warm Starting CMA-ES

  • WS-CMA-ES addresses transfer HPO settings by using source-task observations to warm-start CMA-ES, which otherwise lacks a mechanism to exploit them.The method is built around definitions of a promising distribution and task similarity.Source: §3 · pp. 2–3

3.1 Definition of Task Similarity

  • The γ-promising distribution represents regions likely to contain promising solutions, relying on objective continuity and local convexity of promising regions.Its smoothness distinguishes it from a uniform distribution over the promising set, which assigns zero probability outside that set.Source: §3.1 · p. 3
  • γ-similarity compares source and target promising distributions against a non-informative prior, with positive similarity indicating the source distribution is closer to the target distribution.The measure is formulated using KL divergences between the distributions.Source: §3.1 · p. 3, §3.2 · p. 3

3.2 Algorithm Construction

  • The transfer algorithm selects the top γ × 100% source solutions, builds a Gaussian mixture model from them, and approximates it to initialize CMA-ES.When source and target tasks are treated as similar, initialization uses the source task’s promising region rather than a non-informative prior.Source: §3.2 · p. 3

Estimation of a Promising Distribution of a Source Task

Transferring Prior Knowledge to the CMA-ES

  • The initial CMA-ES Gaussian is chosen by minimizing KL divergence to the source promising distribution, yielding its mean and covariance parameters.The covariance estimate includes a regularizing term, and a diagonal-covariance variant is called WS-sep-CMA-ES.Source: Transferring Prior Knowledge to the… · p. 4

4 Experiments on Synthetic Problems

On synthetic problems, WS-CMA-ES improvement tracked γ-similarity across source-task offsets. The proposed warm-starting methods were more robust to task differences than naïve transfer methods, whose performance deteriorated when offsets changed.

4.1 Performance Depending on Task Similarity

  • The similarity experiments compared CMA-ES and WS-CMA-ES on sphere and rotated ellipsoid tasks, with target offset b = 0.6 and source offsets from b = 0.4 to 0.8.Each setting was run 20 times; the rotated ellipsoid is non-separable and ill-conditioned.Source: §4.1 · p. 4
  • Across source offsets, γ-similarity variation tracked WS-CMA-ES improvement over CMA-ES: transfer worked for similar tasks but not low-similarity tasks.Figure 1 plots the prior parameter b for warm-starting settings using source knowledge from b = 0.6.Source: Figure 1 · p. 4, §4.1 · p. 4

4.2 When Na¨ıve Transfer Fails

  • WS-CMA-ES and WS-sep-CMA-ES were more robust to source-target offset changes than naïve transfer methods, which deteriorated as tasks diverged.ReuseNormal performed best when source and target offsets matched but deteriorated sharply when the offset changed; ReuseGMM was also strongly affected by dissimilarity.Source: Figure 2 · p. 5, §4.2 · p. 5
  • The naïve comparisons included ReuseGMM, which samples from the source promising distribution, and ReuseNormal, which initializes from the source CMA-ES final Gaussian.Random search supplied source-task optimization for methods other than ReuseNormal; CMA-ES and sep-CMA-ES served as non-transfer references.Source: §4.2 · p. 5

5 Experiments for Hyperparameter Optimization

The experiments evaluate warm starting from a dataset subset or another dataset against CMA-ES and several other HPO methods. WS-CMA-ES finds better settings sooner in the reported subset and cross-dataset experiments, while subset-ratio results associate larger subsets with faster convergence.

5 Experiments for Hyperparameter Optimization

  • The experiments covered subset- and other-dataset transfer, compared seven HPO baselines, used 100 random-search settings as shared prior knowledge, and ran each optimization 12 times.The baselines included CMA-ES, random search, WS-only, GP-EI, TPE, MTBO, and MT-BOHAMIANN.Source: §5 · p. 5

LightGBM on Multilabel Classification

MLP on MNIST and Fashion-MNIST

Results and Discussion on Knowledge Transfer of a Subset

  • WS-CMA-ES and WS-only found better settings earlier than CMA-ES, while WS-CMA-ES later converged to better solutions than WS-only.Under the limited evaluation budget, few distribution updates made WS-CMA-ES and WS-only behave similarly.Source: Figure 3 · p. 6, Results and Discussion on Knowledge… · p. 6
  • Higher subset ratios of 2%, 10%, and 50% tended to yield faster convergence, consistent with promising hyperparameters being spatially closer across tasks even when their best values differ.The passage relates this interpretation to Swersky, Snoek, and Adams (2013).Source: Figure 4 · p. 6, Results and Discussion on Knowledge… · p. 6

CNN on CIFAR-100

Using the Knowledge of MLP on MNIST for MLP on Fashion-MNIST

Results and Discussion on the Knowledge Transfer of Another dataset

  • WS-CMA-ES found better settings than CMA-ES after approximately 25 evaluations with subset data and 30 with another dataset; MTBO required approximately 40 evaluations in the latter experiments to beat GP-EI.The authors suggest transfer from another dataset is harder than transfer from a subset.Source: Figure 5 · p. 7, Results and Discussion on the… · p. 7

6 Related Work and Discussion

The discussion distinguishes WS-CMA-ES from warm-started Bayesian optimization in how it uses source-task results and handles task differences. It also notes that objective scales can vary across tasks.

Related Work and Discussion

  • WS-CMA-ES uses source-task results only to initialize optimization, so its computational complexity does not depend on the number of observations.Most warm-starting BO methods repeatedly build a probabilistic model from prior knowledge.Source: §6 · p. 7
  • WS-CMA-ES can initialize the search from source-task results without extra computational complexity or dataset meta-features.The passage notes that meta-features are not always available.Source: §6 · p. 7
  • Objective scales may vary across tasks, a challenge for most BO approaches; Salinas, Shen, and Perrone (2020) introduced a semi-parametric approach for heterogeneous scales.Source: §6 · p. 7

7 Conclusion and Future Work

The paper concludes that WS-CMA-ES initializes CMA-ES from a source task’s promising distribution, with experiments supporting its effectiveness under low budgets and imperfect task similarity. Its key limitation is the assumption that source and target tasks are similar.

7 Conclusion and Future Work

  • WS-CMA-ES initializes the CMA-ES distribution by approximating a source task’s promising distribution, and experiments support effectiveness with low budgets or tasks that are not very similar.The method is designed using definitions of promising distribution and task similarity.Source: §7 · p. 7
  • When source-target similarity is low, WS-CMA-ES can perform worse than CMA-ES; the authors identify detecting dissimilarity and switching back as essential for reliability.Source: §7 · p. 7

A Details of Experimental Setups

The appendix specifies implementation and parameter settings for the HPO and synthetic experiments. Synthetic evaluations used 20 runs and 50 evaluations per problem.

A Details of Experimental Setups

  • The HPO experiments used pycma for CMA-ES and WS-CMA-ES, BoTorch for GP-EI and MTBO, and transplanted RoBO and Hyperopt implementations for MT-BOHAMIANN and TPE.The optimization runs used AI Bridging Cloud Infrastructure with an NVIDIA Tesla V100 GPU and Intel Xeon Gold 6148 CPU; one warm-start setting took about six days.Source: A Details of Experimental Setups · p. 10
  • CMA-ES used λ = 8 and an initial N(0.5, 0.22) distribution; WS-CMA-ES used α = γ = 0.1, and BO methods used 10 initial samples.The authors report robustness to variations in α and γ in Section E.Source: A Details of Experimental Setups · p. 10

B Details of Synthetic Problems

  • The synthetic problems used 20 runs and 50 evaluations each, with γ1 and γ2 set to 0.1 and γ-similarity calculated by Monte Carlo.Table 1 reports the mean and standard error of the best evaluation value; b is the coefficient for the prior task used in warm starting.Source: B Details of Synthetic Problems · p. 10

C Experimental Settings for Hyperparameter Optimization

The HPO experiments use training and validation data, with model- and dataset-specific configurations for LightGBM, MLP, and CNN.

C Experimental Settings for Hyperparameter Optimization

  • Datasets were split 80% for training and 20% for validation, and integer parameters were rounded.Training subsets were formed using a specified fraction of the training data.Source: C Experimental Settings for… · p. 10

C.1 Details of the Experiments for LightGBM

  • Dataset preprocessing was implemented identically, and mean column-wise ROC AUC was measured by 5-fold cross-validation; the optimized hyperparameters are those shown in Table 2.Source: §C.1 · p. 10

C.2 Details of the Experiments for MLP

  • MLP experiments used random crops for training, central crops for validation, and 20 epochs of Nesterov-accelerated stochastic gradient descent.Both MNIST and Fashion-MNIST contain 50,000 examples.Source: §C.2 · p. 10

C.3 CNN on CIFAR-100

  • CNN experiments used the stated CIFAR-10, CIFAR-100, and SVHN preprocessing and trained for 160 epochs with Nesterov-accelerated stochastic gradient descent.The CNN architecture is given in Table 6.Source: §C.3 · p. 10

D Warm Starting Using a Result of Another Dataset: Extra Results

The supplementary experiments test warm starting in the reverse knowledge-transfer directions, using results from more difficult datasets as prior knowledge. WS-CMA-ES still finds better hyperparameter settings faster than CMA-ES in both settings, though its performance advantage is less pronounced.

D Warm Starting Using a Result of Another Dataset: Extra Results

E.1 MLPs on MNIST

The MNIST MLP experiments test WS-CMA-ES sensitivity to α and γ using prior knowledge from one-tenth of the complete MNIST data.

E.1 MLPs on MNIST

  • The sensitivity experiments optimized MNIST-trained MLPs using prior knowledge from one-tenth of complete MNIST.The MLP hyperparameters are listed in Table 3.Source: §E.1 · p. 11, Table 3 · p. 11
  • WS-CMA-ES outperformed CMA-ES at every tested α value, despite the trade-off between overfitting the source task at low α and approaching a uniform distribution at high α.The tested α values ranged from 0.05 to 0.25, with γ fixed at 0.1.Source: §E.1 · pp. 11–12
  • WS-CMA-ES outperformed CMA-ES at every tested γ value, but performance became slightly worse as γ increased; the authors recommend γ ≈ 0.1.Very small γ can overfit the promising distribution to the prior task, while very large γ moves it toward uniformity.Source: §E.1 · p. 12

E.2 Problem with Task Dissimilarity

On a task-dissimilar rotated-ellipsoid problem, WS-CMA-ES is sensitive to very small α or γ, while the authors report robust performance with the main-paper settings α = 0.1 and γ = 0.1.

E.2 Problem with Task Dissimilarity

  • The sensitivity experiments applied varying α and γ to a rotated ellipsoid function with offset b = 0.2, a task-dissimilar case.The study identifies this as a case of task dissimilarity in Section 4.2.Source: §E.2 · p. 12
  • CMA-ES performed slightly better than WS-CMA-ES; WS-CMA-ES was broadly robust to α, but α = 0.05 showed slightly unstable behavior.The authors attribute this instability to small α overtrusting source-task information.Source: §E.2 · p. 12, Figure 8 · p. 13
  • CMA-ES performed better than WS-CMA-ES; WS-CMA-ES was broadly robust to γ, but γ = 0.05 showed unstable behavior.The authors attribute this to promising-region estimates becoming overfitted to the source task when γ is too small.Source: §E.2 · p. 12, Figure 8 · p. 13
  • The authors recommend α = 0.1 and γ = 0.1 even without prior information about source-target similarity, based on robust performance in this task-dissimilar experiment.These were also the settings used in the main paper.Source: §E.2 · p. 12

Related papers

Loading 2012.06932v1…