Unify the univariate and multivariate TPE #2618

HideakiImamura · 2021-04-22T05:25:18Z

Depends on #2615 and #2616.

Part of works for #2614.

Motivation

The univariate TPE is a special case of the multivariate TPE, but the implementation of them in Optuna is overwrapped now. This PR aims to resolve the redundancy.

It seems to be difficult to support full backward compatibility including the behavior when the seed is fixed. The reason is that mus, sigmas, and weights in multivariate TPE are arranged in the order of observation, while those in current univariate TPE are arranged in the order of ascending mus. In this PR, we will adapt our logic to the multivariate TPE. We will verify through benchmarking experiments that the performance of the univariate TPE is not significantly impaired by this change.

Description of the changes

Unify the univariate and multivariate TPE
Fix some tests

TODOs

Performance benchmark on kurobako

Benchmark Results

I took a benchmark between this PR and the current master. In summary, the changes made by this PR do not significantly impair the performance of the algorithm.

Environments:

optuna: this PR (9d25958) and the current master (be407fd)
python: 3.8
kurobako: 0.2.9
algorithms: multivariate-tpe-master-PRUNER, multivariate-tpe-this-PR-PRUNER, tpe-master-PRUNER, tpe-this-PR-PRUNER

Each algorithm was run 100 times with the same settings, and the mean and variance of the performance were plotted.

Results

With NopPruner

With MedianPruner

With HyperbandPruner

codecov-commenter · 2021-04-22T05:39:58Z

Codecov Report

Merging #2618 (71db3fc) into master (bfb41ab) will decrease coverage by 0.02%.
The diff coverage is 98.93%.

@@            Coverage Diff             @@
##           master    #2618      +/-   ##
==========================================
- Coverage   91.66%   91.64%   -0.03%     
==========================================
  Files         140      139       -1     
  Lines       11522    11311     -211     
==========================================
- Hits        10562    10366     -196     
+ Misses        960      945      -15

Impacted Files	Coverage Δ
optuna/samplers/_tpe/parzen_estimator.py	`98.87% <98.80%> (-1.13%)`	⬇️
optuna/samplers/_tpe/sampler.py	`94.66% <100.00%> (+1.02%)`	⬆️
optuna/_callbacks.py	`100.00% <0.00%> (ø)`
optuna/storages/__init__.py	`100.00% <0.00%> (ø)`
optuna/integration/allennlp.py	`88.17% <0.00%> (+0.05%)`	⬆️

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update bfb41ab...71db3fc. Read the comment docs.

github-actions · 2021-05-09T23:05:12Z

This pull request has not seen any recent activity.

HideakiImamura · 2021-05-13T03:22:14Z

I took a benchmark between this PR and the current master. In summary, the changes made by this PR do not significantly impair the performance of the algorithm.

Environments:

optuna: this PR (9d25958) and the current master (be407fd)
python: 3.8
kurobako: 0.2.9

Each algorithm was run 100 times with the same settings, and the mean and variance of the performance were plotted.

Results

With NopPruner

With MedianPruner

With HyperbandPruner

HideakiImamura · 2021-05-14T02:54:28Z

@himkt @Crissman Let me remove assignments of this PR since you already have a lot of assigned PRs.

@c-bata @hvy Could you review this PR if you have time?

c-bata · 2021-05-14T08:33:33Z

@HideakiImamura Could you please assign another reviewer instead of me?

HideakiImamura · 2021-05-17T02:23:48Z

@c-bata Sure! Let me remove the assignment.

hvy · 2021-05-17T03:36:03Z

Assigned @keisuke-umezawa !

hvy · 2021-05-17T06:26:39Z

Could you reduce the diff now that #2615 is merged?

hvy · 2021-05-20T04:31:49Z

Sorry, could you merge the latest master again? I just merge #2616 .

HideakiImamura · 2021-05-27T10:36:45Z

@hvy Thanks for your careful reviews. I updated the code following your suggestions. PTAL.

I take a benchmark with the NAS bench (C) to test the floating value.

HideakiImamura · 2021-05-27T12:07:25Z

@hvy @keisuke-umezawa I have benchmarked and updated the results using the latest version, modified based on the discussion during the previous mob review. There appears to be generally no difference between this PR and master. PTAL.

hvy

Thanks a lot for the updated benchmarks and plots. They look promising 👍

optuna/samplers/_tpe/parzen_estimator.py

HideakiImamura · 2021-05-28T06:05:27Z

@hvy Thank you for your helpful and insightful reviews. I updated the code following your suggestions.

I simplify the logic of _calculate_numerical_params
I add the logic considering the consider_endpoints flag
I bring up some test cases for the univariate TPE to test consider_endpoints, consider_magic_clip, and consider_prior.

PTAL.

HideakiImamura · 2021-05-28T06:10:16Z

Note: Currently, the _ParzenEstimator calculates mus, sigmas, and weights, taking into account observations outside of [low, high] during init. The restriction to the [low, high] range is done when the sample method is called. This mechanism gives unexpected results in the estimation of sigmas.

This is due to the fact that when calculating the sigmas in _calculate_numerical_params, the mus is sorted and then the low and high are added. This can be avoided by adding low and high and then sorting mus, but changing the algorithm is out of the scope of this PR and will not be addressed here. We will leave this issue for future work.

keisuke-umezawa · 2021-05-28T08:28:04Z

optuna/samplers/_tpe/sampler.py

+        # If ``multivariate`` = True and ``group`` = True, we ignore the trials that are not
+        # included in each subspace.
+        # If ``multivariate`` = False, we consider such trials.
+        if multivariate and any([param_name not in trial.params for param_name in param_names]):


In my understanding, the procedure of calculation does not depend on multivariate, because multivariate is always true when any([param_name not in trial.params for param_name in param_names]) is true. If my understanding is correct, I think we can omit multivariate from the arguments of this method.

Sorry for the confusion. Here, we want to check any([param_name not in trial.params for param_name in param_names]) only when multivariate = True. In the current master, we don't check any([param_name not in trial.params for param_name in param_names]) when multivariate = False, so for the consistency, I include multivariate here.

I updated the code comment like: If multivariate = False, we skip the check

keisuke-umezawa

Other than the calculation of sigmas, LGTM! I will check it again after the discussion of sigmas is settled.

keisuke-umezawa · 2021-05-28T08:54:22Z

optuna/samplers/_tpe/parzen_estimator.py

+        sorted_mus_with_endpoints = np.asarray([], dtype=float)
+        prior_mu = 0.5 * (low + high)
+        prior_sigma = 1.0 * (high - low)
+
        if consider_prior:


I can decrease the number of nest from 2 to 1 by the following code.

if consider_prior: mus = np.empty(n_observations + 1) mus[:n_observations] = observations mus[n_observations] = prior_mu sigmas = np.empty(n_observations + 1) sigmas[n_observations] = prior_sigma else: mus = observations sigmas = np.empty(n_observations) if multivariate: assert sigmas0 is not None sigmas[:n_observations] = sigmas0 * (high - low) else: assert sigmas0 is None sorted_indices = np.argsort(mus) sorted_mus = mus[sorted_indices] sorted_mus_with_endpoints = np.empty(len(mus) + 2, dtype=float) sorted_mus_with_endpoints[0] = low sorted_mus_with_endpoints[1:-1] = sorted_mus sorted_mus_with_endpoints[-1] = high sorted_sigmas = np.maximum( sorted_mus_with_endpoints[1:-1] - sorted_mus_with_endpoints[0:-2], sorted_mus_with_endpoints[2:] - sorted_mus_with_endpoints[1:-1], ) sigmas[:n_observations] = sorted_sigmas[np.argsort(sorted_indices)]

If it is better for readability, could you use the above snippet?

Looks great. Thanks for your insightful review!

HideakiImamura · 2021-05-31T05:49:34Z

@keisuke-umezawa Thanks for your reviews! I updated the codes following your suggestions. PTAL.

hvy

Thanks for the updates. The code around the mus and sigmas are simpler now.

By the way, are the benchmarks difficult to run? I'm wondering if we should run another round since there has been some changes.

tests/samplers_tests/tpe_tests/test_parzen_estimator.py

optuna/samplers/_tpe/parzen_estimator.py

HideakiImamura · 2021-06-01T00:49:40Z

@hvy Thanks for your review! I applied all of your suggestions. PTAL.

By the way, I can re-run the benchmark experiments easily. This PR will be merged after the release of v2.8.0, so I think we should have the latest benchmark result.

hvy · 2021-06-01T01:06:33Z

By the way, I can re-run the benchmark experiments easily. This PR will be merged after the release of v2.8.0, so I think we should have the latest benchmark result.

Sounds great, let's do that. 👍

hvy · 2021-06-03T07:40:40Z

Note: Benchmarks have been updated.

keisuke-umezawa

LGTM! Thank you for the long PR.

hvy

Great work and thanks, LGTM given the benchmarks and the many discussions!

hvy · 2021-06-08T01:10:20Z

Updated the label to compatibility as per suggestion by @not522 . Thanks.

Unify univariate and multivariate TPE

9d25958

HideakiImamura added the enhancement Change that does not break compatibility and not affect public interfaces, but improves performance. label Apr 22, 2021

github-actions bot added the optuna.samplers Related to the `optuna.samplers` submodule. This is automatically labeled by github-actions. label Apr 22, 2021

HideakiImamura mentioned this pull request Apr 22, 2021

A major refactoring of Tree-structured Parzen Estimator #2614

Closed

6 tasks

HideakiImamura marked this pull request as draft April 22, 2021 07:34

toshihikoyanase assigned Crissman and himkt Apr 23, 2021

github-actions bot added the stale Exempt from stale bot labeling. label May 9, 2021

hvy mentioned this pull request May 11, 2021

Constant liar for TPESampler #2664

Merged

github-actions bot removed the stale Exempt from stale bot labeling. label May 13, 2021

HideakiImamura assigned c-bata and hvy and unassigned Crissman and himkt May 14, 2021

HideakiImamura unassigned c-bata May 17, 2021

hvy assigned keisuke-umezawa May 17, 2021

HideakiImamura mentioned this pull request May 17, 2021

Separate MOTPESampler from TPESampler #2616

Merged

Merge branch 'master' into unify-univariate-and-multivariate-tpe

4871476

HideakiImamura mentioned this pull request May 19, 2021

Unify MOTPESampler and TPESampler #2688

Merged

2 tasks

Merge branch 'master' into unify-univariate-and-multivariate-tpe

65665fa

HideakiImamura marked this pull request as ready for review May 20, 2021 04:44

Follow reviews

a793be2

HideakiImamura added 3 commits May 27, 2021 19:39

Appoly formatter

f39e471

Merge branch 'master' into unify-univariate-and-multivariate-tpe

6cc3625

Use ndarray of pairs & improve locality

590f74c

hvy reviewed May 27, 2021

View reviewed changes

optuna/samplers/_tpe/parzen_estimator.py Show resolved Hide resolved

hvy reviewed May 28, 2021

View reviewed changes

optuna/samplers/_tpe/parzen_estimator.py Outdated Show resolved Hide resolved

Fix calculate logic and endpoints logic and add tests

b74e381

keisuke-umezawa reviewed May 28, 2021

View reviewed changes

Follwo review comments

59b563c

hvy reviewed May 31, 2021

View reviewed changes

tests/samplers_tests/tpe_tests/test_parzen_estimator.py Outdated Show resolved Hide resolved

optuna/samplers/_tpe/parzen_estimator.py Outdated Show resolved Hide resolved

optuna/samplers/_tpe/parzen_estimator.py Outdated Show resolved Hide resolved

Apply review commnts

71db3fc

hvy added this to the v2.9.0 milestone Jun 1, 2021

keisuke-umezawa approved these changes Jun 5, 2021

View reviewed changes

hvy approved these changes Jun 7, 2021

View reviewed changes

hvy merged commit 92bbec2 into optuna:master Jun 7, 2021

hvy added compatibility Change that breaks compatibility. and removed enhancement Change that does not break compatibility and not affect public interfaces, but improves performance. labels Jun 8, 2021

tohmae mentioned this pull request Jun 9, 2021

Add CatBoostPruningCallback #2734

Merged

not522 mentioned this pull request Jul 20, 2021

Speed up TPESampler #2816

Merged

HideakiImamura deleted the unify-univariate-and-multivariate-tpe branch June 9, 2023 02:22

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Unify the univariate and multivariate TPE #2618

Unify the univariate and multivariate TPE #2618

HideakiImamura commented Apr 22, 2021 •

edited

codecov-commenter commented Apr 22, 2021 •

edited

github-actions bot commented May 9, 2021

HideakiImamura commented May 13, 2021

HideakiImamura commented May 14, 2021

c-bata commented May 14, 2021

HideakiImamura commented May 17, 2021

hvy commented May 17, 2021

hvy commented May 17, 2021

hvy commented May 20, 2021

HideakiImamura commented May 27, 2021

HideakiImamura commented May 27, 2021

hvy left a comment

HideakiImamura commented May 28, 2021

HideakiImamura commented May 28, 2021

keisuke-umezawa May 28, 2021 •

edited

HideakiImamura May 31, 2021

HideakiImamura May 31, 2021

keisuke-umezawa left a comment •

edited

keisuke-umezawa May 28, 2021 •

edited

HideakiImamura May 31, 2021

HideakiImamura commented May 31, 2021

hvy left a comment

HideakiImamura commented Jun 1, 2021

hvy commented Jun 1, 2021

hvy commented Jun 3, 2021

keisuke-umezawa left a comment

hvy left a comment

hvy commented Jun 8, 2021

Unify the univariate and multivariate TPE #2618

Unify the univariate and multivariate TPE #2618

Conversation

HideakiImamura commented Apr 22, 2021 • edited

Motivation

Description of the changes

TODOs

Benchmark Results

Environments:

Results

codecov-commenter commented Apr 22, 2021 • edited

Codecov Report

github-actions bot commented May 9, 2021

HideakiImamura commented May 13, 2021

Environments:

Results

HideakiImamura commented May 14, 2021

c-bata commented May 14, 2021

HideakiImamura commented May 17, 2021

hvy commented May 17, 2021

hvy commented May 17, 2021

hvy commented May 20, 2021

HideakiImamura commented May 27, 2021

HideakiImamura commented May 27, 2021

hvy left a comment

Choose a reason for hiding this comment

HideakiImamura commented May 28, 2021

HideakiImamura commented May 28, 2021

keisuke-umezawa May 28, 2021 • edited

Choose a reason for hiding this comment

HideakiImamura May 31, 2021

Choose a reason for hiding this comment

HideakiImamura May 31, 2021

Choose a reason for hiding this comment

keisuke-umezawa left a comment • edited

Choose a reason for hiding this comment

keisuke-umezawa May 28, 2021 • edited

Choose a reason for hiding this comment

HideakiImamura May 31, 2021

Choose a reason for hiding this comment

HideakiImamura commented May 31, 2021

hvy left a comment

Choose a reason for hiding this comment

HideakiImamura commented Jun 1, 2021

hvy commented Jun 1, 2021

hvy commented Jun 3, 2021

keisuke-umezawa left a comment

Choose a reason for hiding this comment

hvy left a comment

Choose a reason for hiding this comment

hvy commented Jun 8, 2021

HideakiImamura commented Apr 22, 2021 •

edited

codecov-commenter commented Apr 22, 2021 •

edited

keisuke-umezawa May 28, 2021 •

edited

keisuke-umezawa left a comment •

edited

keisuke-umezawa May 28, 2021 •

edited