Add `HyperbandPruner` by crcrpar · Pull Request #809 · optuna/optuna

crcrpar · 2019-12-18T10:31:13Z

~~This depends on #808~~
The algorithm would behave differently from the paper if the sampler is TPESampler because there is no way to filter out the trials of brackets other than that of the running trial.

Although #785 and #805 are for Hyperband, this PR follows another design policy.
The core design of #785 is to realize filtering by adding an attribute that represents pruner to Trial.
It will make Study more complex while it can keep the current loosely connected relationship between Sampler and Pruner.

On the other hand, the policy of this PR does not implement any filtering of trials.
This means that we will need to add some interaction between HyperbandPruner and Sampler, especially TPESampler.

EDIT:
In this implementation, trials are filtered by bracket_id that is computed by HyperbandPruner._get_bracket_id and this filtering is enabled by implementing _BracketStudy which just wraps Study for the HyperbandPruner use only. The idea is suggested in #809 (comment).

codecov-io · 2019-12-18T10:49:07Z

Codecov Report

❗ No coverage uploaded for pull request base (master@2ebb157). Click here to learn what that means.
The diff coverage is 100%.

@@            Coverage Diff            @@
##             master     #809   +/-   ##
=========================================
  Coverage          ?   90.13%           
=========================================
  Files             ?      108           
  Lines             ?     8914           
  Branches          ?        0           
=========================================
  Hits              ?     8035           
  Misses            ?      879           
  Partials          ?        0

Impacted Files	Coverage Δ
optuna/pruners/base.py	`62.5% <ø> (ø)`
setup.py	`0% <ø> (ø)`
optuna/study.py	`93.62% <100%> (ø)`
optuna/pruners/hyperband.py	`78.57% <100%> (ø)`

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 2ebb157...7bc4874. Read the comment docs.

optuna/pruners/successive_halving.py

sile

Thank you for the swift update. The current design looks good for me.
By the way, I left some minor comments about the code detail.

optuna/pruners/hyperband.py

hvy · 2019-12-20T09:37:08Z

optuna/pruners/hyperband.py

+        return self._n_pruners
+
+
+class _BracketStudy(Study):


Other methods besides get_trials might behaive unexpectedly as they are not filtered. I believe we can either override and raise, or avoid inheriting from Study.

I tried to disable other methods of Study in a naive way. PTAL.

optuna/pruners/hyperband.py

tests/pruners_tests/test_hyperband.py

optuna/pruners/hyperband.py

crcrpar · 2019-12-26T06:26:29Z

As to n_brackets, following #809 (comment) and #809 (comment), I'd like to make it defaults to 4.

(This is the clarification as the discussion is getting long and not accessible.)

c-bata

LGTM with nits!! I think current implementation is reasonable for now 👍 Good job @crcrpar.

optuna/pruners/hyperband.py

crcrpar · 2019-12-26T08:33:20Z

Discussed how to compute budgets and allocate trials to brackets with @sile, and one way is to merge this without any modification because

currently, there doesn't seem to be any colossal problem like poor performance
it might take a long time to design a reasonable algorithm and the PR for it might be not tiny

I don't mean we should stop here, merge first without further improvement. From the perspective of the granularity and duration of the PR, merging is one option.

optuna/pruners/hyperband.py

optuna/study.py

optuna/pruners/hyperband.py

…hyperband

hvy

LGTM!

crcrpar · 2020-01-14T05:34:28Z

Thank you all for the review and discussion. Though this PR satisfies the condition to get merged, I'd like to add TODO comment about resource allocation to brackets. Thank you for your understanding beforehand.

…

On Thu, Jan 9, 2020 at 18:10 Hiroyuki Vincent Yamazaki < ***@***.***> wrote: ***@***.**** approved this pull request. LGTM! — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#809?email_source=notifications&email_token=AD3Q7U5FA7PXESFAHYK5ESTQ43SZ5A5CNFSM4J4IZEZKYY3PNVWWK3TUL52HS4DFWFIHK3DMKJSXC5LFON2FEZLWNFSXPKTDN5WW2ZLOORPWSZGOCRE3OIY#pullrequestreview-340375331>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AD3Q7UY55TF64IPMV3GGTOTQ43SZ5ANCNFSM4J4IZEZA> .

crcrpar · 2020-01-15T06:55:51Z

Added the TODO.

sile · 2020-01-15T09:13:22Z

Added the TODO.

Thanks!
I'll merge this PR.

PhilipMay · 2020-02-08T07:37:22Z

Thanks for this implementation! It's awsome! :-)

sile reviewed Dec 19, 2019

View reviewed changes

optuna/pruners/successive_halving.py Outdated Show resolved Hide resolved

crcrpar force-pushed the naive-hyperband branch 3 times, most recently from 0921c30 to 584286b Compare December 19, 2019 08:44

sile requested changes Dec 20, 2019

View reviewed changes

optuna/pruners/hyperband.py Outdated Show resolved Hide resolved

optuna/pruners/hyperband.py Show resolved Hide resolved

optuna/pruners/hyperband.py Outdated Show resolved Hide resolved

optuna/pruners/hyperband.py Outdated Show resolved Hide resolved

hvy reviewed Dec 20, 2019

View reviewed changes

optuna/pruners/hyperband.py Outdated Show resolved Hide resolved

hvy reviewed Dec 20, 2019

View reviewed changes

optuna/pruners/hyperband.py Outdated Show resolved Hide resolved

hvy reviewed Dec 20, 2019

View reviewed changes

optuna/pruners/hyperband.py Outdated Show resolved Hide resolved

hvy reviewed Dec 20, 2019

View reviewed changes

optuna/pruners/hyperband.py Outdated Show resolved Hide resolved

crcrpar mentioned this pull request Dec 25, 2019

Add trials to *Sampler.sample_{independent, relative} #805

Closed

crcrpar commented Dec 25, 2019

View reviewed changes

optuna/pruners/hyperband.py Show resolved Hide resolved

crcrpar commented Dec 25, 2019

View reviewed changes

tests/pruners_tests/test_hyperband.py Outdated Show resolved Hide resolved

c-bata reviewed Dec 25, 2019

View reviewed changes

optuna/pruners/hyperband.py Show resolved Hide resolved

crcrpar requested a review from hvy December 25, 2019 09:45

sile reviewed Dec 26, 2019

View reviewed changes

optuna/pruners/hyperband.py Outdated Show resolved Hide resolved

c-bata reviewed Dec 26, 2019

View reviewed changes

optuna/pruners/hyperband.py Outdated Show resolved Hide resolved

crcrpar added a commit to crcrpar/optuna that referenced this pull request Dec 26, 2019

reflect optuna#809 (comment)

da2c5ee

c-bata approved these changes Dec 26, 2019

View reviewed changes

optuna/pruners/hyperband.py Outdated Show resolved Hide resolved

sile requested changes Dec 26, 2019

View reviewed changes

optuna/pruners/hyperband.py Outdated Show resolved Hide resolved

optuna/pruners/hyperband.py Outdated Show resolved Hide resolved

crcrpar added 7 commits December 26, 2019 18:18

add hyperband pruner

28fcfc1

reorder imports

752b6d2

remove warning tests

83e0dab

access comments

e27cb83

refine _BracketStudy

3a6ec36

prefix _ and reflect comments

850b091

fix import error

aabcff0

sile mentioned this pull request Dec 27, 2019

Implement Hyperband pruner #785

Closed

hvy reviewed Jan 6, 2020

View reviewed changes

optuna/pruners/hyperband.py Outdated Show resolved Hide resolved

hvy reviewed Jan 6, 2020

View reviewed changes

optuna/pruners/hyperband.py Outdated Show resolved Hide resolved

hvy reviewed Jan 6, 2020

View reviewed changes

optuna/study.py Show resolved Hide resolved

hvy reviewed Jan 6, 2020

View reviewed changes

optuna/pruners/hyperband.py Outdated Show resolved Hide resolved

crcrpar added 4 commits January 6, 2020 23:52

clarify what paper is referred

3a3d3d5

cosmetic fix

2ebb157

Merge branch 'master' of https://github.com/optuna/optuna into naive-…

b81548a

…hyperband

add python logging's warning

4297c51

crcrpar mentioned this pull request Jan 8, 2020

Update TPESampler to support HyperbandPruner #828

Merged

sile removed this from the v1.0.0 milestone Jan 9, 2020

hvy added this to the v1.1.0 milestone Jan 9, 2020

fix import

f00fc2e

crcrpar requested a review from hvy January 9, 2020 06:03

hvy approved these changes Jan 9, 2020

View reviewed changes

add TODO

7bc4874

crcrpar added a commit to crcrpar/optuna that referenced this pull request Jan 15, 2020

reflect optuna#809 (comment)

af0b4c4

sile merged commit 0db5508 into optuna:master Jan 15, 2020

crcrpar mentioned this pull request Jan 17, 2020

Change TPESampler to support Hyperband crcrpar/optuna#1

Closed

crcrpar deleted the naive-hyperband branch January 21, 2020 05:50

toshihikoyanase mentioned this pull request Jan 31, 2020

Faster CmaEsSampler #798

Closed

hvy mentioned this pull request Feb 5, 2020

Sampler restart #823

Closed

himkt mentioned this pull request Mar 5, 2020

Implement ThresholdPruner. #963

Merged

3 tasks

sile mentioned this pull request Apr 24, 2020

Improve the trial allocation algorithm of HyperbandPruner #1141

Merged

toshihikoyanase mentioned this pull request Nov 9, 2021

Hyperband bracket assignment using hash in parallelization #3083

Closed

zaburo-ch mentioned this pull request Nov 6, 2022

Stop using hash function in _get_bracket_id in HyperbandPruner #4131

Merged

Uh oh!

Conversation

crcrpar commented Dec 18, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

codecov-io commented Dec 18, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

Uh oh!

sile left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

hvy Dec 20, 2019

Choose a reason for hiding this comment

Uh oh!

crcrpar Dec 25, 2019

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

crcrpar commented Dec 26, 2019

Uh oh!

c-bata left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

crcrpar commented Dec 26, 2019

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

hvy left a comment

Choose a reason for hiding this comment

Uh oh!

crcrpar commented Jan 14, 2020 via email

Uh oh!

crcrpar commented Jan 15, 2020

Uh oh!

sile commented Jan 15, 2020

Uh oh!

PhilipMay commented Feb 8, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

crcrpar commented Dec 18, 2019 •

edited

Loading

codecov-io commented Dec 18, 2019 •

edited

Loading