Implement `Hyperband` pruner by crcrpar · Pull Request #785 · optuna/optuna

crcrpar · 2019-12-11T05:37:39Z

UPDATE
The original version is separated into #805 and this PR.

This PR is based on #301.

Intuitively, Hyperband (HB) eliminates the dependency on parameters of SuccessiveHalving (SH) by internally executes multiple SHs with different configurations.

Design

Study with HyperbandPruner runs in the same way as with other pruners. HyperbandPruner class maintains some number of SuccessiveHalvingPruners (= brackets) and selects a pruner for each Trial. So, the algorithm would be different from the paper to some extent. There're two challenges, 1) different trials of the same Study have to be pruned by different brackets, and 2) When sampling for a new trial, Sampler can only use the trials of the same bracket.

Major Changes

Study collects the list of trials (= friend_trials in the code) and set it as a Trial's attribute
- To filter trials with some metadata, study sets the information of pruner as user_attr to Trial and uses it as a filter.
Trial passes its friend_trial to study.sampler
Sampler's sampling methods accept the list of trials as their argument

An alternative design, a new class that manages multiple Studys is implemented in https://github.com/crcrpar/optuna/tree/dev/study-manager.

codecov-io · 2019-12-11T10:23:29Z

Codecov Report

Merging #785 into master will decrease coverage by 0.12%.
The diff coverage is 85.54%.

@@            Coverage Diff             @@
##           master     #785      +/-   ##
==========================================
- Coverage   90.15%   90.02%   -0.13%     
==========================================
  Files         106      108       +2     
  Lines        8769     8906     +137     
==========================================
+ Hits         7906     8018     +112     
- Misses        863      888      +25

Impacted Files	Coverage Δ
optuna/pruners/__init__.py	`100% <100%> (ø)`	⬆️
optuna/samplers/tpe/sampler.py	`87.54% <100%> (ø)`	⬆️
optuna/pruners/percentile.py	`95.71% <100%> (+0.25%)`	⬆️
tests/test_study.py	`97.9% <100%> (ø)`	⬆️
optuna/study.py	`93.82% <100%> (+0.3%)`	⬆️
optuna/integration/cma.py	`94.03% <100%> (+0.08%)`	⬆️
optuna/integration/skopt.py	`88.42% <100%> (ø)`	⬆️
optuna/pruners/successive_halving.py	`95.23% <100%> (+0.41%)`	⬆️
optuna/testing/integration.py	`100% <100%> (ø)`	⬆️
optuna/integration/lightgbm_tuner/optimize.py	`76.03% <100%> (ø)`	⬆️
... and 12 more

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 0389962...4195bea. Read the comment docs.

crcrpar · 2019-12-11T07:17:22Z

optuna/pruners/base.py

+
+        return ''
+
+    def should_filter_trials(self):


This method is called when Study's construction and tells the study whether the study's sampler can use all the trials or not.

crcrpar · 2019-12-11T07:18:07Z

optuna/study.py


        self.sampler = sampler or samplers.TPESampler()
        self.pruner = pruner or pruners.MedianPruner()
+        self._should_filter_trials = self.pruner.should_filter_trials()


Ref: https://github.com/optuna/optuna/pull/785/files#diff-2fd97cdb5b16d80b081b14de09821a7cR41

crcrpar · 2019-12-11T07:21:16Z

optuna/study.py

+        trial_pruner_metadata = self.pruner.__class__.__name__
+        pruner_auxiliary_data = self.pruner.get_trial_pruner_auxiliary_data(
+            self._study_id, trial.number)
+        if pruner_auxiliary_data:
+            trial_pruner_metadata += pruner_auxiliary_data
+        trial.set_user_attr('pruner_metadata', trial_pruner_metadata)


All Trial has an attribute of what pruner is used as a user_attr to allow for filtering by pruner information.

crcrpar · 2019-12-11T13:52:47Z

optuna/trial.py

+        self._friend_trials = None  # type: Optional[List[FrozenTrial]]
+
+    def _set_friend_trials(self, friend_trials):
+        # type: (List[FrozenTrial]) -> None
+
+        self._friend_trials = friend_trials
+
+    def _clear_friend_trials(self):
+        # type: () -> None
+
+        self._friend_trials = None
+
+    @property
+    def friend_trials(self):
+        # type: () -> Optional[List[FrozenTrial]]
+
+        return self._friend_trials


I don't think the naming of friend_trials is cool 😅

crcrpar · 2019-12-11T14:33:48Z

As I have done in general and I want to get any feedback, so I mark this as ready for review.

crcrpar

Do I have to avoid the deprecated study._study_id and use study.study_name instead as done in these comments?

crcrpar · 2019-12-12T05:09:43Z

optuna/pruners/base.py

        raise NotImplementedError
+
+    @abc.abstractmethod
+    def get_trial_pruner_auxiliary_data(self, study_id, trial_number):


As study_id is deprecated, should this be study_name as follows?

Suggested change

def get_trial_pruner_auxiliary_data(self, study_id, trial_number):

def get_trial_pruner_auxiliary_data(self, study_name, trial_number):

crcrpar · 2019-12-12T05:10:40Z

optuna/pruners/base.py

+
+    @abc.abstractmethod
+    def get_trial_pruner_auxiliary_data(self, study_id, trial_number):
+        # type: (int, int) -> str


Reflecting the above change.

Suggested change

# type: (int, int) -> str

# type: (str, int) -> str

crcrpar · 2019-12-12T05:11:36Z

optuna/pruners/hyperband.py

+            budget += n / 2
+        return budget
+
+    def get_bracket_id(self, study_id, trial_number):


As mentioned above, study_id is deprecated.

Suggested change

def get_bracket_id(self, study_id, trial_number):

def get_bracket_id(self, study_name, trial_number):

crcrpar · 2019-12-12T05:11:46Z

optuna/pruners/hyperband.py

+        return budget
+
+    def get_bracket_id(self, study_id, trial_number):
+        # type: (int, int) -> int


ditto

Suggested change

# type: (int, int) -> int

# type: (str, int) -> int

crcrpar · 2019-12-12T05:12:16Z

optuna/pruners/hyperband.py

+        # type: (int, int) -> int
+        """Computes the id of bracket for a trial of `trial_number`."""
+
+        n = hash('{}_{}'.format(study_id, trial_number)) % self._resource_badget


ditto

Suggested change

n = hash('{}_{}'.format(study_id, trial_number)) % self._resource_badget

n = hash('{}_{}'.format(study_name, trial_number)) % self._resource_badget

crcrpar · 2019-12-12T05:13:07Z

optuna/pruners/percentile.py

        return best_intermediate_result > p
+
+    def get_trial_pruner_auxiliary_data(self, study_id, trial_number):
+        # type: (int, int) -> str


Suggested change

# type: (int, int) -> str

# type: (str, int) -> str

crcrpar · 2019-12-12T05:13:28Z

optuna/pruners/successive_halving.py


            rung += 1

+    def get_trial_pruner_auxiliary_data(self, study_id, trial_number):


Suggested change

def get_trial_pruner_auxiliary_data(self, study_id, trial_number):

def get_trial_pruner_auxiliary_data(self, study_name, trial_number):

crcrpar · 2019-12-12T05:13:58Z

optuna/pruners/successive_halving.py

            rung += 1

+    def get_trial_pruner_auxiliary_data(self, study_id, trial_number):
+        # type: (int, int) -> str


Suggested change

# type: (int, int) -> str

# type: (str, int) -> str

crcrpar · 2019-12-12T05:14:27Z

optuna/testing/integration.py


        return self.is_pruning

+    def get_trial_pruner_auxiliary_data(self, study_id, trial_number):


Suggested change

def get_trial_pruner_auxiliary_data(self, study_id, trial_number):

def get_trial_pruner_auxiliary_data(self, study_name, trial_number):

crcrpar · 2019-12-12T05:14:35Z

optuna/testing/integration.py

        return self.is_pruning

+    def get_trial_pruner_auxiliary_data(self, study_id, trial_number):
+        # type: (int, int) -> str


Suggested change

# type: (int, int) -> str

# type: (str, int) -> str

c-bata

Good job @crcrpar!
My code review is still work in progress (Actually, I still don't understand the reason why this PR includes the change of sampler interface, and what friend_trials means.). For now, I put some minor comments.

c-bata · 2019-12-12T08:57:55Z

optuna/testing/sampler.py

        if len(study.trials) > 1:
            raise RuntimeError("`FirstTrialOnlyRandomSampler` only works on the first trial.")

        return super(FirstTrialOnlyRandomSampler, self).sample_relative(study, trial, search_space)


It looks trials argument should be propagated.

Suggested change

return super(FirstTrialOnlyRandomSampler, self).sample_relative(study, trial, search_space)

return super(FirstTrialOnlyRandomSampler, self).sample_relative(study, trial, search_space, trials=trials)

sample_independent method (L80) is also.

Good catch, thank you!

optuna/pruners/hyperband.py

c-bata · 2019-12-12T14:17:58Z

optuna/pruners/hyperband.py

+        `Hyperband paper <http://www.jmlr.org/papers/volume18/16-558/16-558.pdf>`_.
+        """
+
+        n = hash('{}_{}'.format(study_id, trial_number)) % self._resource_badget


I'm not confident but It looks trial_number % self._resource_budget is enough, right?

Suggested change

n = hash('{}_{}'.format(study_id, trial_number)) % self._resource_badget

n = trial_number % self._resource_budget

optuna/pruners/hyperband.py

crcrpar · 2019-12-13T07:27:38Z

@c-bata

Thank you for your review!
Being not complete is not a problem.
I really appreciate your response. 😀

why this PR includes the change of sampler interface, and what friend_trials means

I think your question is equivalent to why new argument trials: List[FrozenTrial].
A sampler, especially TPE sampler, must only reflect the trials that have the same SuccessiveHalvingPruner of HyperbandPruner as a trial that is currently being initialized.
To realize this, I added an attribute of pruner_metadata to Trial via set_uesr_atttr inside Study. Also, make Study collects appropriate trials and set them as friend_trials to the trial tentatively for the ease of trial selection.

I hope this helps you.

c-bata · 2019-12-13T09:29:07Z

Thank you! Probably, I understand.

When using SuccessiveHalvingPruner, it has no problem to use the last intermediate score of pruned trials.
But it seems that HyperbandPruner is not.
So you labeled trials as pruned_metadata (this is a string representation of bracket_id in HyperbandPruner) by get_trial_pruner_auxiliary_data() method.
friend_trials returns the trials which has the same pruned_metadata (bracket_id).
So you passes friend_trials to samplers.

update other samplers

update tests

crcrpar · 2019-12-18T04:51:10Z

This PR consists of two major changes

new argument of trials to samplers sample methods
hyperband

Both changes are not trivial I think, thus I'd like to separate this into two PRs.

sile · 2019-12-18T06:13:47Z

Both changes are not trivial I think, thus I'd like to separate this into two PRs.

Nice idea!

sile · 2019-12-27T02:05:08Z

I think that this PR was taken over by #809. Could we close this? > @crcrpar

crcrpar · 2019-12-27T02:23:31Z

I think that this PR was taken over by #809. Could we close this? > @crcrpar

thank you for your reminding, of course.

c-bata mentioned this pull request Dec 11, 2019

Bandit-based early stopping algorithm c-bata/goptuna#5

Closed

4 tasks

crcrpar force-pushed the dev/hyperband branch from 1bbf155 to d97f324 Compare December 11, 2019 09:11

crcrpar commented Dec 11, 2019

View reviewed changes

crcrpar marked this pull request as ready for review December 11, 2019 14:33

crcrpar commented Dec 12, 2019

View reviewed changes

c-bata reviewed Dec 12, 2019

View reviewed changes

c-bata mentioned this pull request Dec 13, 2019

HyperbandPruner c-bata/goptuna#63

Closed

crcrpar mentioned this pull request Dec 18, 2019

Faster CmaEsSampler #798

Closed

crcrpar added 2 commits December 18, 2019 13:38

take list of trials as an input

14a1fa5

update other samplers

set the list of trials to Trial

d91a2e7

update tests

crcrpar mentioned this pull request Dec 18, 2019

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

Closed

crcrpar added 3 commits December 18, 2019 14:38

new pruner methods for hyperband

48d8dc4

add hyperband

82a97c7

update study tests

887e64c

use study_name not study_id

4195bea

crcrpar force-pushed the dev/hyperband branch from d3f749a to 4195bea Compare December 18, 2019 06:34

hvy mentioned this pull request Dec 18, 2019

Refactoring of successive halving. #808

Merged

crcrpar mentioned this pull request Dec 18, 2019

Add HyperbandPruner #809

Merged

crcrpar closed this Dec 27, 2019

crcrpar deleted the dev/hyperband branch January 22, 2020 12:05

	def get_trial_pruner_auxiliary_data(self, study_id, trial_number):
	def get_trial_pruner_auxiliary_data(self, study_name, trial_number):

	def get_bracket_id(self, study_id, trial_number):
	def get_bracket_id(self, study_name, trial_number):

	n = hash('{}_{}'.format(study_id, trial_number)) % self._resource_badget
	n = hash('{}_{}'.format(study_name, trial_number)) % self._resource_badget


		rung += 1

		def get_trial_pruner_auxiliary_data(self, study_id, trial_number):


		return self.is_pruning

		def get_trial_pruner_auxiliary_data(self, study_id, trial_number):

	return super(FirstTrialOnlyRandomSampler, self).sample_relative(study, trial, search_space)
	return super(FirstTrialOnlyRandomSampler, self).sample_relative(study, trial, search_space, trials=trials)

	n = hash('{}_{}'.format(study_id, trial_number)) % self._resource_badget
	n = trial_number % self._resource_budget

Uh oh!

Conversation

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

Uh oh!

Design

Major Changes

Uh oh!

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

Uh oh!

Codecov Report

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

crcrpar commented Dec 11, 2019

Uh oh!

crcrpar left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

c-bata left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

c-bata Dec 12, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

crcrpar commented Dec 13, 2019

Uh oh!

c-bata commented Dec 13, 2019

Uh oh!

crcrpar commented Dec 18, 2019

Uh oh!

sile commented Dec 18, 2019

Uh oh!

sile commented Dec 27, 2019

Uh oh!

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

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

crcrpar commented Dec 11, 2019 •

edited

Loading

codecov-io commented Dec 11, 2019 •

edited

Loading

c-bata Dec 12, 2019 •

edited

Loading

crcrpar commented Dec 27, 2019 •

edited

Loading