We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
Hyperband Usage Documentation
First many thanks for the new hyperband pruner.

I would like to request some more information on how to use it. I guess that it is necessary to tune the default parameters. Maybe you could provide some more information then just link to the papers. When should I set which parameter to what value?

The paper talks about an infinite horizon setting. Since I often do not set the number of iterations on optuna but stop it with KeyboardInterrupt is that relevant for me?

Many thanks
Philip

--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `optuna/pruners/hyperband.py`
Content:
```
1 import math
2 from typing import List
3 from typing import Optional
4 import warnings
5 
6 import optuna
7 from optuna._experimental import experimental
8 from optuna import logging
9 from optuna.pruners.base import BasePruner
10 from optuna.pruners.successive_halving import SuccessiveHalvingPruner
11 from optuna.trial import FrozenTrial
12 
13 _logger = logging.get_logger(__name__)
14 
15 
16 @experimental("1.1.0")
17 class HyperbandPruner(BasePruner):
18     """Pruner using Hyperband.
19 
20     As SuccessiveHalving (SHA) requires the number of configurations
21     :math:`n` as its hyperparameter.  For a given finite budget :math:`B`,
22     all the configurations have the resources of :math:`B \\over n` on average.
23     As you can see, there will be a trade-off of :math:`B` and :math:`B \\over n`.
24     `Hyperband <http://www.jmlr.org/papers/volume18/16-558/16-558.pdf>`_ attacks this trade-off
25     by trying different :math:`n` values for a fixed budget.
26 
27     .. note::
28         * In the Hyperband paper, the counterpart of :class:`~optuna.samplers.RandomSampler`
29           is used.
30         * Optuna uses :class:`~optuna.samplers.TPESampler` by default.
31         * `The benchmark result
32           <https://github.com/optuna/optuna/pull/828#issuecomment-575457360>`_
33           shows that :class:`optuna.pruners.HyperbandPruner` supports both samplers.
34 
35     .. note::
36         If you use ``HyperbandPruner`` with :class:`~optuna.samplers.TPESampler`,
37         it's recommended to consider to set larger ``n_trials`` or ``timeout`` to make full use of
38         the characteristics of :class:`~optuna.samplers.TPESampler`
39         because :class:`~optuna.samplers.TPESampler` uses some (by default, :math:`10`)
40         :class:`~optuna.trial.Trial`\\ s for its startup.
41 
42         As Hyperband runs multiple :class:`~optuna.pruners.SuccessiveHalvingPruner` and collect
43         trials based on the current :class:`~optuna.trial.Trial`\\ 's bracket ID, each bracket
44         needs to observe more than :math:`10` :class:`~optuna.trial.Trial`\\ s
45         for :class:`~optuna.samplers.TPESampler` to adapt its search space.
46 
47         Thus, for example, if ``HyperbandPruner`` has :math:`4` pruners in it,
48         at least :math:`4 \\times 10` trials are consumed for startup.
49 
50     .. note::
51         Hyperband has several :class:`~optuna.pruners.SuccessiveHalvingPruner`. Each
52         :class:`~optuna.pruners.SuccessiveHalvingPruner` is referred as "bracket" in the original
53         paper. The number of brackets is an important factor to control the early stopping behavior
54         of Hyperband and is automatically determined by ``max_resource`` and ``reduction_factor``
55         as `The number of brackets = floor(log(max_resource) / log(reduction_factor)) + 1`. Please
56         set ``reduction_factor`` so that the number of brackets is not too large　(about 4 ~ 6 in
57         most use cases).　Please see Section 3.6 of the `original paper
58         <http://www.jmlr.org/papers/volume18/16-558/16-558.pdf>`_ for the detail.
59 
60     Args:
61         min_resource:
62             A parameter for specifying the minimum resource allocated to a trial noted as :math:`r`
63             in the paper.
64             See the details for :class:`~optuna.pruners.SuccessiveHalvingPruner`.
65         max_resource:
66             A parameter for specifying the maximum resource allocated to a trial noted as :math:`R`
67             in the paper. This value represents and should match the maximum iteration steps (e.g.,
68             the number of epochs for neural networks).
69         reduction_factor:
70             A parameter for specifying reduction factor of promotable trials noted as
71             :math:`\\eta` in the paper. See the details for
72             :class:`~optuna.pruners.SuccessiveHalvingPruner`.
73         n_brackets:
74 
75             .. deprecated:: 1.4.0
76                 This argument will be removed from :class:`~optuna.pruners.HyperbandPruner`. The
77                 number of brackets are automatically determined based on ``max_resource`` and
78                 ``reduction_factor``.
79 
80             The number of :class:`~optuna.pruners.SuccessiveHalvingPruner`\\ s (brackets).
81             Defaults to :math:`4`.
82         min_early_stopping_rate_low:
83 
84             .. deprecated:: 1.4.0
85                 This argument will be removed from :class:`~optuna.pruners.HyperbandPruner`.
86 
87             A parameter for specifying the minimum early-stopping rate.
88             This parameter is related to a parameter that is referred to as :math:`s` and used in
89             `Asynchronous SuccessiveHalving paper <http://arxiv.org/abs/1810.05934>`_.
90             The minimum early stopping rate for :math:`i` th bracket is :math:`i + s`.
91     """
92 
93     def __init__(
94         self,
95         min_resource: int = 1,
96         max_resource: int = 80,
97         reduction_factor: int = 3,
98         n_brackets: Optional[int] = None,
99         min_early_stopping_rate_low: Optional[int] = None,
100     ) -> None:
101 
102         self._pruners = []  # type: List[SuccessiveHalvingPruner]
103         self._reduction_factor = reduction_factor
104         self._total_trial_allocation_budget = 0
105 
106         if n_brackets is None:
107             # In the original paper http://www.jmlr.org/papers/volume18/16-558/16-558.pdf, the
108             # inputs of Hyperband are `R`: max resource and `\eta`: reduction factor. The
109             # number of brackets (this is referred as `s_{max} + 1` in the paper) is calculated
110             # by s_{max} + 1 = \floor{\log_{\eta} (R)} + 1 in Algorithm 1 of the original paper.
111             self._n_brackets = (
112                 math.floor(math.log2(max_resource) / math.log2(reduction_factor)) + 1
113             )
114         else:
115             message = (
116                 "The argument of `n_brackets` is deprecated. "
117                 "The number of brackets is automatically determined by `max_resource` and "
118                 "`reduction_factor` as "
119                 "`n_brackets = floor(log(max_resource) / log(reduction_factor)) + 1`. "
120                 "Please specify `reduction_factor` appropriately."
121             )
122             warnings.warn(message, DeprecationWarning)
123             _logger.warning(message)
124             self._n_brackets = n_brackets
125 
126         self._trial_allocation_budgets = []  # type: List[int]
127 
128         _logger.debug("Hyperband has {} brackets".format(self._n_brackets))
129 
130         for i in range(self._n_brackets):
131             trial_allocation_budget = self._calculate_trial_allocation_budget(i)
132             self._total_trial_allocation_budget += trial_allocation_budget
133             self._trial_allocation_budgets.append(trial_allocation_budget)
134 
135             # N.B. (crcrpar): `min_early_stopping_rate` has the information of `bracket_index`.
136             if min_early_stopping_rate_low is None:
137                 min_early_stopping_rate = i
138             else:
139                 message = (
140                     "The argument of `min_early_stopping_rate_low` is deprecated. "
141                     "Please specify `min_resource` appropriately."
142                 )
143                 warnings.warn(message, DeprecationWarning)
144                 _logger.warning(message)
145                 min_early_stopping_rate = min_early_stopping_rate_low + i
146 
147             _logger.debug(
148                 "{}th bracket has minimum early stopping rate of {}".format(
149                     i, min_early_stopping_rate
150                 )
151             )
152 
153             pruner = SuccessiveHalvingPruner(
154                 min_resource=min_resource,
155                 reduction_factor=reduction_factor,
156                 min_early_stopping_rate=min_early_stopping_rate,
157             )
158             self._pruners.append(pruner)
159 
160     def prune(self, study: "optuna.study.Study", trial: FrozenTrial) -> bool:
161         i = self._get_bracket_id(study, trial)
162         _logger.debug("{}th bracket is selected".format(i))
163         bracket_study = self._create_bracket_study(study, i)
164         return self._pruners[i].prune(bracket_study, trial)
165 
166     def _calculate_trial_allocation_budget(self, pruner_index: int) -> int:
167         """Compute the trial allocated budget for a bracket of ``pruner_index``.
168 
169         In the `original paper <http://www.jmlr.org/papers/volume18/16-558/16-558.pdf>`, the
170         number of trials per one bracket is referred as ``n`` in Algorithm 1. Since we do not know
171         the total number of trials in the leaning scheme of Optuna, we calculate the ratio of the
172         number of trials here instead.
173         """
174 
175         s = self._n_brackets - 1 - pruner_index
176         return math.ceil(self._n_brackets * (self._reduction_factor ** s) / (s + 1))
177 
178     def _get_bracket_id(self, study: "optuna.study.Study", trial: FrozenTrial) -> int:
179         """Compute the index of bracket for a trial of ``trial_number``.
180 
181         The index of a bracket is noted as :math:`s` in
182         `Hyperband paper <http://www.jmlr.org/papers/volume18/16-558/16-558.pdf>`_.
183         """
184 
185         n = (
186             hash("{}_{}".format(study.study_name, trial.number))
187             % self._total_trial_allocation_budget
188         )
189         for i in range(self._n_brackets):
190             n -= self._trial_allocation_budgets[i]
191             if n < 0:
192                 return i
193 
194         assert False, "This line should be unreachable."
195 
196     def _create_bracket_study(
197         self, study: "optuna.study.Study", bracket_index: int
198     ) -> "optuna.study.Study":
199         # This class is assumed to be passed to
200         # `SuccessiveHalvingPruner.prune` in which `get_trials`,
201         # `direction`, and `storage` are used.
202         # But for safety, prohibit the other attributes explicitly.
203         class _BracketStudy(optuna.study.Study):
204 
205             _VALID_ATTRS = (
206                 "get_trials",
207                 "direction",
208                 "_storage",
209                 "_study_id",
210                 "pruner",
211                 "study_name",
212                 "_bracket_id",
213                 "sampler",
214             )
215 
216             def __init__(self, study: "optuna.study.Study", bracket_id: int) -> None:
217                 super().__init__(
218                     study_name=study.study_name,
219                     storage=study._storage,
220                     sampler=study.sampler,
221                     pruner=study.pruner,
222                 )
223                 self._bracket_id = bracket_id
224 
225             def get_trials(self, deepcopy: bool = True) -> List[FrozenTrial]:
226                 trials = super().get_trials(deepcopy=deepcopy)
227                 pruner = self.pruner
228                 assert isinstance(pruner, HyperbandPruner)
229                 return [t for t in trials if pruner._get_bracket_id(self, t) == self._bracket_id]
230 
231             def __getattribute__(self, attr_name):  # type: ignore
232                 if attr_name not in _BracketStudy._VALID_ATTRS:
233                     raise AttributeError(
234                         "_BracketStudy does not have attribute of '{}'".format(attr_name)
235                     )
236                 else:
237                     return object.__getattribute__(self, attr_name)
238 
239         return _BracketStudy(study, bracket_index)
240
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/optuna/pruners/hyperband.py b/optuna/pruners/hyperband.py
--- a/optuna/pruners/hyperband.py
+++ b/optuna/pruners/hyperband.py
@@ -57,10 +57,58 @@
         most use cases).　Please see Section 3.6 of the `original paper
         <http://www.jmlr.org/papers/volume18/16-558/16-558.pdf>`_ for the detail.
 
+    Example:
+
+        We minimize an objective function with Hyperband pruning algorithm.
+
+        .. testsetup::
+
+            import numpy as np
+            from sklearn.model_selection import train_test_split
+
+            np.random.seed(seed=0)
+            X = np.random.randn(200).reshape(-1, 1)
+            y = np.where(X[:, 0] < 0.5, 0, 1)
+            X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0)
+            classes = np.unique(y)
+
+        .. testcode::
+
+            import optuna
+            from sklearn.linear_model import SGDClassifier
+
+            n_train_iter = 100
+
+            def objective(trial):
+                alpha = trial.suggest_uniform('alpha', 0.0, 1.0)
+                clf = SGDClassifier(alpha=alpha)
+
+                for step in range(n_train_iter):
+                    clf.partial_fit(X_train, y_train, classes=classes)
+
+                    intermediate_value = clf.score(X_test, y_test)
+                    trial.report(intermediate_value, step)
+
+                    if trial.should_prune():
+                        raise optuna.exceptions.TrialPruned()
+
+                return clf.score(X_test, y_test)
+
+            study = optuna.create_study(
+                direction='maximize',
+                pruner=optuna.pruners.HyperbandPruner(
+                    min_resource=1,
+                    max_resource=n_train_iter,
+                    reduction_factor=3
+                )
+            )
+            study.optimize(objective, n_trials=20)
+
     Args:
         min_resource:
             A parameter for specifying the minimum resource allocated to a trial noted as :math:`r`
-            in the paper.
+            in the paper. A smaller :math:`r` will give a result faster, but a larger
+            :math:`r` will give a better guarantee of successful judging between configurations.
             See the details for :class:`~optuna.pruners.SuccessiveHalvingPruner`.
         max_resource:
             A parameter for specifying the maximum resource allocated to a trial noted as :math:`R`
@@ -68,8 +116,8 @@
             the number of epochs for neural networks).
         reduction_factor:
             A parameter for specifying reduction factor of promotable trials noted as
-            :math:`\\eta` in the paper. See the details for
-            :class:`~optuna.pruners.SuccessiveHalvingPruner`.
+            :math:`\\eta` in the paper.
+            See the details for :class:`~optuna.pruners.SuccessiveHalvingPruner`.
         n_brackets:
 
             .. deprecated:: 1.4.0

{"golden_diff": "diff --git a/optuna/pruners/hyperband.py b/optuna/pruners/hyperband.py\n--- a/optuna/pruners/hyperband.py\n+++ b/optuna/pruners/hyperband.py\n@@ -57,10 +57,58 @@\n         most use cases).\u3000Please see Section 3.6 of the `original paper\n         <http://www.jmlr.org/papers/volume18/16-558/16-558.pdf>`_ for the detail.\n \n+    Example:\n+\n+        We minimize an objective function with Hyperband pruning algorithm.\n+\n+        .. testsetup::\n+\n+            import numpy as np\n+            from sklearn.model_selection import train_test_split\n+\n+            np.random.seed(seed=0)\n+            X = np.random.randn(200).reshape(-1, 1)\n+            y = np.where(X[:, 0] < 0.5, 0, 1)\n+            X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0)\n+            classes = np.unique(y)\n+\n+        .. testcode::\n+\n+            import optuna\n+            from sklearn.linear_model import SGDClassifier\n+\n+            n_train_iter = 100\n+\n+            def objective(trial):\n+                alpha = trial.suggest_uniform('alpha', 0.0, 1.0)\n+                clf = SGDClassifier(alpha=alpha)\n+\n+                for step in range(n_train_iter):\n+                    clf.partial_fit(X_train, y_train, classes=classes)\n+\n+                    intermediate_value = clf.score(X_test, y_test)\n+                    trial.report(intermediate_value, step)\n+\n+                    if trial.should_prune():\n+                        raise optuna.exceptions.TrialPruned()\n+\n+                return clf.score(X_test, y_test)\n+\n+            study = optuna.create_study(\n+                direction='maximize',\n+                pruner=optuna.pruners.HyperbandPruner(\n+                    min_resource=1,\n+                    max_resource=n_train_iter,\n+                    reduction_factor=3\n+                )\n+            )\n+            study.optimize(objective, n_trials=20)\n+\n     Args:\n         min_resource:\n             A parameter for specifying the minimum resource allocated to a trial noted as :math:`r`\n-            in the paper.\n+            in the paper. A smaller :math:`r` will give a result faster, but a larger\n+            :math:`r` will give a better guarantee of successful judging between configurations.\n             See the details for :class:`~optuna.pruners.SuccessiveHalvingPruner`.\n         max_resource:\n             A parameter for specifying the maximum resource allocated to a trial noted as :math:`R`\n@@ -68,8 +116,8 @@\n             the number of epochs for neural networks).\n         reduction_factor:\n             A parameter for specifying reduction factor of promotable trials noted as\n-            :math:`\\\\eta` in the paper. See the details for\n-            :class:`~optuna.pruners.SuccessiveHalvingPruner`.\n+            :math:`\\\\eta` in the paper.\n+            See the details for :class:`~optuna.pruners.SuccessiveHalvingPruner`.\n         n_brackets:\n \n             .. deprecated:: 1.4.0\n", "issue": "Hyperband Usage Documentation\nFirst many thanks for the new hyperband pruner.\r\n\r\nI would like to request some more information on how to use it. I guess that it is necessary to tune the default parameters. Maybe you could provide some more information then just link to the papers. When should I set which parameter to what value?\r\n\r\nThe paper talks about an infinite horizon setting. Since I often do not set the number of iterations on optuna but stop it with KeyboardInterrupt is that relevant for me?\r\n\r\nMany thanks\r\nPhilip\n", "before_files": [{"content": "import math\nfrom typing import List\nfrom typing import Optional\nimport warnings\n\nimport optuna\nfrom optuna._experimental import experimental\nfrom optuna import logging\nfrom optuna.pruners.base import BasePruner\nfrom optuna.pruners.successive_halving import SuccessiveHalvingPruner\nfrom optuna.trial import FrozenTrial\n\n_logger = logging.get_logger(__name__)\n\n\n@experimental(\"1.1.0\")\nclass HyperbandPruner(BasePruner):\n    \"\"\"Pruner using Hyperband.\n\n    As SuccessiveHalving (SHA) requires the number of configurations\n    :math:`n` as its hyperparameter.  For a given finite budget :math:`B`,\n    all the configurations have the resources of :math:`B \\\\over n` on average.\n    As you can see, there will be a trade-off of :math:`B` and :math:`B \\\\over n`.\n    `Hyperband <http://www.jmlr.org/papers/volume18/16-558/16-558.pdf>`_ attacks this trade-off\n    by trying different :math:`n` values for a fixed budget.\n\n    .. note::\n        * In the Hyperband paper, the counterpart of :class:`~optuna.samplers.RandomSampler`\n          is used.\n        * Optuna uses :class:`~optuna.samplers.TPESampler` by default.\n        * `The benchmark result\n          <https://github.com/optuna/optuna/pull/828#issuecomment-575457360>`_\n          shows that :class:`optuna.pruners.HyperbandPruner` supports both samplers.\n\n    .. note::\n        If you use ``HyperbandPruner`` with :class:`~optuna.samplers.TPESampler`,\n        it's recommended to consider to set larger ``n_trials`` or ``timeout`` to make full use of\n        the characteristics of :class:`~optuna.samplers.TPESampler`\n        because :class:`~optuna.samplers.TPESampler` uses some (by default, :math:`10`)\n        :class:`~optuna.trial.Trial`\\\\ s for its startup.\n\n        As Hyperband runs multiple :class:`~optuna.pruners.SuccessiveHalvingPruner` and collect\n        trials based on the current :class:`~optuna.trial.Trial`\\\\ 's bracket ID, each bracket\n        needs to observe more than :math:`10` :class:`~optuna.trial.Trial`\\\\ s\n        for :class:`~optuna.samplers.TPESampler` to adapt its search space.\n\n        Thus, for example, if ``HyperbandPruner`` has :math:`4` pruners in it,\n        at least :math:`4 \\\\times 10` trials are consumed for startup.\n\n    .. note::\n        Hyperband has several :class:`~optuna.pruners.SuccessiveHalvingPruner`. Each\n        :class:`~optuna.pruners.SuccessiveHalvingPruner` is referred as \"bracket\" in the original\n        paper. The number of brackets is an important factor to control the early stopping behavior\n        of Hyperband and is automatically determined by ``max_resource`` and ``reduction_factor``\n        as `The number of brackets = floor(log(max_resource) / log(reduction_factor)) + 1`. Please\n        set ``reduction_factor`` so that the number of brackets is not too large\u3000(about 4 ~ 6 in\n        most use cases).\u3000Please see Section 3.6 of the `original paper\n        <http://www.jmlr.org/papers/volume18/16-558/16-558.pdf>`_ for the detail.\n\n    Args:\n        min_resource:\n            A parameter for specifying the minimum resource allocated to a trial noted as :math:`r`\n            in the paper.\n            See the details for :class:`~optuna.pruners.SuccessiveHalvingPruner`.\n        max_resource:\n            A parameter for specifying the maximum resource allocated to a trial noted as :math:`R`\n            in the paper. This value represents and should match the maximum iteration steps (e.g.,\n            the number of epochs for neural networks).\n        reduction_factor:\n            A parameter for specifying reduction factor of promotable trials noted as\n            :math:`\\\\eta` in the paper. See the details for\n            :class:`~optuna.pruners.SuccessiveHalvingPruner`.\n        n_brackets:\n\n            .. deprecated:: 1.4.0\n                This argument will be removed from :class:`~optuna.pruners.HyperbandPruner`. The\n                number of brackets are automatically determined based on ``max_resource`` and\n                ``reduction_factor``.\n\n            The number of :class:`~optuna.pruners.SuccessiveHalvingPruner`\\\\ s (brackets).\n            Defaults to :math:`4`.\n        min_early_stopping_rate_low:\n\n            .. deprecated:: 1.4.0\n                This argument will be removed from :class:`~optuna.pruners.HyperbandPruner`.\n\n            A parameter for specifying the minimum early-stopping rate.\n            This parameter is related to a parameter that is referred to as :math:`s` and used in\n            `Asynchronous SuccessiveHalving paper <http://arxiv.org/abs/1810.05934>`_.\n            The minimum early stopping rate for :math:`i` th bracket is :math:`i + s`.\n    \"\"\"\n\n    def __init__(\n        self,\n        min_resource: int = 1,\n        max_resource: int = 80,\n        reduction_factor: int = 3,\n        n_brackets: Optional[int] = None,\n        min_early_stopping_rate_low: Optional[int] = None,\n    ) -> None:\n\n        self._pruners = []  # type: List[SuccessiveHalvingPruner]\n        self._reduction_factor = reduction_factor\n        self._total_trial_allocation_budget = 0\n\n        if n_brackets is None:\n            # In the original paper http://www.jmlr.org/papers/volume18/16-558/16-558.pdf, the\n            # inputs of Hyperband are `R`: max resource and `\\eta`: reduction factor. The\n            # number of brackets (this is referred as `s_{max} + 1` in the paper) is calculated\n            # by s_{max} + 1 = \\floor{\\log_{\\eta} (R)} + 1 in Algorithm 1 of the original paper.\n            self._n_brackets = (\n                math.floor(math.log2(max_resource) / math.log2(reduction_factor)) + 1\n            )\n        else:\n            message = (\n                \"The argument of `n_brackets` is deprecated. \"\n                \"The number of brackets is automatically determined by `max_resource` and \"\n                \"`reduction_factor` as \"\n                \"`n_brackets = floor(log(max_resource) / log(reduction_factor)) + 1`. \"\n                \"Please specify `reduction_factor` appropriately.\"\n            )\n            warnings.warn(message, DeprecationWarning)\n            _logger.warning(message)\n            self._n_brackets = n_brackets\n\n        self._trial_allocation_budgets = []  # type: List[int]\n\n        _logger.debug(\"Hyperband has {} brackets\".format(self._n_brackets))\n\n        for i in range(self._n_brackets):\n            trial_allocation_budget = self._calculate_trial_allocation_budget(i)\n            self._total_trial_allocation_budget += trial_allocation_budget\n            self._trial_allocation_budgets.append(trial_allocation_budget)\n\n            # N.B. (crcrpar): `min_early_stopping_rate` has the information of `bracket_index`.\n            if min_early_stopping_rate_low is None:\n                min_early_stopping_rate = i\n            else:\n                message = (\n                    \"The argument of `min_early_stopping_rate_low` is deprecated. \"\n                    \"Please specify `min_resource` appropriately.\"\n                )\n                warnings.warn(message, DeprecationWarning)\n                _logger.warning(message)\n                min_early_stopping_rate = min_early_stopping_rate_low + i\n\n            _logger.debug(\n                \"{}th bracket has minimum early stopping rate of {}\".format(\n                    i, min_early_stopping_rate\n                )\n            )\n\n            pruner = SuccessiveHalvingPruner(\n                min_resource=min_resource,\n                reduction_factor=reduction_factor,\n                min_early_stopping_rate=min_early_stopping_rate,\n            )\n            self._pruners.append(pruner)\n\n    def prune(self, study: \"optuna.study.Study\", trial: FrozenTrial) -> bool:\n        i = self._get_bracket_id(study, trial)\n        _logger.debug(\"{}th bracket is selected\".format(i))\n        bracket_study = self._create_bracket_study(study, i)\n        return self._pruners[i].prune(bracket_study, trial)\n\n    def _calculate_trial_allocation_budget(self, pruner_index: int) -> int:\n        \"\"\"Compute the trial allocated budget for a bracket of ``pruner_index``.\n\n        In the `original paper <http://www.jmlr.org/papers/volume18/16-558/16-558.pdf>`, the\n        number of trials per one bracket is referred as ``n`` in Algorithm 1. Since we do not know\n        the total number of trials in the leaning scheme of Optuna, we calculate the ratio of the\n        number of trials here instead.\n        \"\"\"\n\n        s = self._n_brackets - 1 - pruner_index\n        return math.ceil(self._n_brackets * (self._reduction_factor ** s) / (s + 1))\n\n    def _get_bracket_id(self, study: \"optuna.study.Study\", trial: FrozenTrial) -> int:\n        \"\"\"Compute the index of bracket for a trial of ``trial_number``.\n\n        The index of a bracket is noted as :math:`s` in\n        `Hyperband paper <http://www.jmlr.org/papers/volume18/16-558/16-558.pdf>`_.\n        \"\"\"\n\n        n = (\n            hash(\"{}_{}\".format(study.study_name, trial.number))\n            % self._total_trial_allocation_budget\n        )\n        for i in range(self._n_brackets):\n            n -= self._trial_allocation_budgets[i]\n            if n < 0:\n                return i\n\n        assert False, \"This line should be unreachable.\"\n\n    def _create_bracket_study(\n        self, study: \"optuna.study.Study\", bracket_index: int\n    ) -> \"optuna.study.Study\":\n        # This class is assumed to be passed to\n        # `SuccessiveHalvingPruner.prune` in which `get_trials`,\n        # `direction`, and `storage` are used.\n        # But for safety, prohibit the other attributes explicitly.\n        class _BracketStudy(optuna.study.Study):\n\n            _VALID_ATTRS = (\n                \"get_trials\",\n                \"direction\",\n                \"_storage\",\n                \"_study_id\",\n                \"pruner\",\n                \"study_name\",\n                \"_bracket_id\",\n                \"sampler\",\n            )\n\n            def __init__(self, study: \"optuna.study.Study\", bracket_id: int) -> None:\n                super().__init__(\n                    study_name=study.study_name,\n                    storage=study._storage,\n                    sampler=study.sampler,\n                    pruner=study.pruner,\n                )\n                self._bracket_id = bracket_id\n\n            def get_trials(self, deepcopy: bool = True) -> List[FrozenTrial]:\n                trials = super().get_trials(deepcopy=deepcopy)\n                pruner = self.pruner\n                assert isinstance(pruner, HyperbandPruner)\n                return [t for t in trials if pruner._get_bracket_id(self, t) == self._bracket_id]\n\n            def __getattribute__(self, attr_name):  # type: ignore\n                if attr_name not in _BracketStudy._VALID_ATTRS:\n                    raise AttributeError(\n                        \"_BracketStudy does not have attribute of '{}'\".format(attr_name)\n                    )\n                else:\n                    return object.__getattribute__(self, attr_name)\n\n        return _BracketStudy(study, bracket_index)\n", "path": "optuna/pruners/hyperband.py"}], "after_files": [{"content": "import math\nfrom typing import List\nfrom typing import Optional\nimport warnings\n\nimport optuna\nfrom optuna._experimental import experimental\nfrom optuna import logging\nfrom optuna.pruners.base import BasePruner\nfrom optuna.pruners.successive_halving import SuccessiveHalvingPruner\nfrom optuna.trial import FrozenTrial\n\n_logger = logging.get_logger(__name__)\n\n\n@experimental(\"1.1.0\")\nclass HyperbandPruner(BasePruner):\n    \"\"\"Pruner using Hyperband.\n\n    As SuccessiveHalving (SHA) requires the number of configurations\n    :math:`n` as its hyperparameter.  For a given finite budget :math:`B`,\n    all the configurations have the resources of :math:`B \\\\over n` on average.\n    As you can see, there will be a trade-off of :math:`B` and :math:`B \\\\over n`.\n    `Hyperband <http://www.jmlr.org/papers/volume18/16-558/16-558.pdf>`_ attacks this trade-off\n    by trying different :math:`n` values for a fixed budget.\n\n    .. note::\n        * In the Hyperband paper, the counterpart of :class:`~optuna.samplers.RandomSampler`\n          is used.\n        * Optuna uses :class:`~optuna.samplers.TPESampler` by default.\n        * `The benchmark result\n          <https://github.com/optuna/optuna/pull/828#issuecomment-575457360>`_\n          shows that :class:`optuna.pruners.HyperbandPruner` supports both samplers.\n\n    .. note::\n        If you use ``HyperbandPruner`` with :class:`~optuna.samplers.TPESampler`,\n        it's recommended to consider to set larger ``n_trials`` or ``timeout`` to make full use of\n        the characteristics of :class:`~optuna.samplers.TPESampler`\n        because :class:`~optuna.samplers.TPESampler` uses some (by default, :math:`10`)\n        :class:`~optuna.trial.Trial`\\\\ s for its startup.\n\n        As Hyperband runs multiple :class:`~optuna.pruners.SuccessiveHalvingPruner` and collect\n        trials based on the current :class:`~optuna.trial.Trial`\\\\ 's bracket ID, each bracket\n        needs to observe more than :math:`10` :class:`~optuna.trial.Trial`\\\\ s\n        for :class:`~optuna.samplers.TPESampler` to adapt its search space.\n\n        Thus, for example, if ``HyperbandPruner`` has :math:`4` pruners in it,\n        at least :math:`4 \\\\times 10` trials are consumed for startup.\n\n    .. note::\n        Hyperband has several :class:`~optuna.pruners.SuccessiveHalvingPruner`. Each\n        :class:`~optuna.pruners.SuccessiveHalvingPruner` is referred as \"bracket\" in the original\n        paper. The number of brackets is an important factor to control the early stopping behavior\n        of Hyperband and is automatically determined by ``max_resource`` and ``reduction_factor``\n        as `The number of brackets = floor(log(max_resource) / log(reduction_factor)) + 1`. Please\n        set ``reduction_factor`` so that the number of brackets is not too large\u3000(about 4 ~ 6 in\n        most use cases).\u3000Please see Section 3.6 of the `original paper\n        <http://www.jmlr.org/papers/volume18/16-558/16-558.pdf>`_ for the detail.\n\n    Example:\n\n        We minimize an objective function with Hyperband pruning algorithm.\n\n        .. testsetup::\n\n            import numpy as np\n            from sklearn.model_selection import train_test_split\n\n            np.random.seed(seed=0)\n            X = np.random.randn(200).reshape(-1, 1)\n            y = np.where(X[:, 0] < 0.5, 0, 1)\n            X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0)\n            classes = np.unique(y)\n\n        .. testcode::\n\n            import optuna\n            from sklearn.linear_model import SGDClassifier\n\n            n_train_iter = 100\n\n            def objective(trial):\n                alpha = trial.suggest_uniform('alpha', 0.0, 1.0)\n                clf = SGDClassifier(alpha=alpha)\n\n                for step in range(n_train_iter):\n                    clf.partial_fit(X_train, y_train, classes=classes)\n\n                    intermediate_value = clf.score(X_test, y_test)\n                    trial.report(intermediate_value, step)\n\n                    if trial.should_prune():\n                        raise optuna.exceptions.TrialPruned()\n\n                return clf.score(X_test, y_test)\n\n            study = optuna.create_study(\n                direction='maximize',\n                pruner=optuna.pruners.HyperbandPruner(\n                    min_resource=1,\n                    max_resource=n_train_iter,\n                    reduction_factor=3\n                )\n            )\n            study.optimize(objective, n_trials=20)\n\n    Args:\n        min_resource:\n            A parameter for specifying the minimum resource allocated to a trial noted as :math:`r`\n            in the paper. A smaller :math:`r` will give a result faster, but a larger\n            :math:`r` will give a better guarantee of successful judging between configurations.\n            See the details for :class:`~optuna.pruners.SuccessiveHalvingPruner`.\n        max_resource:\n            A parameter for specifying the maximum resource allocated to a trial noted as :math:`R`\n            in the paper. This value represents and should match the maximum iteration steps (e.g.,\n            the number of epochs for neural networks).\n        reduction_factor:\n            A parameter for specifying reduction factor of promotable trials noted as\n            :math:`\\\\eta` in the paper.\n            See the details for :class:`~optuna.pruners.SuccessiveHalvingPruner`.\n        n_brackets:\n\n            .. deprecated:: 1.4.0\n                This argument will be removed from :class:`~optuna.pruners.HyperbandPruner`. The\n                number of brackets are automatically determined based on ``max_resource`` and\n                ``reduction_factor``.\n\n            The number of :class:`~optuna.pruners.SuccessiveHalvingPruner`\\\\ s (brackets).\n            Defaults to :math:`4`.\n        min_early_stopping_rate_low:\n\n            .. deprecated:: 1.4.0\n                This argument will be removed from :class:`~optuna.pruners.HyperbandPruner`.\n\n            A parameter for specifying the minimum early-stopping rate.\n            This parameter is related to a parameter that is referred to as :math:`s` and used in\n            `Asynchronous SuccessiveHalving paper <http://arxiv.org/abs/1810.05934>`_.\n            The minimum early stopping rate for :math:`i` th bracket is :math:`i + s`.\n    \"\"\"\n\n    def __init__(\n        self,\n        min_resource: int = 1,\n        max_resource: int = 80,\n        reduction_factor: int = 3,\n        n_brackets: Optional[int] = None,\n        min_early_stopping_rate_low: Optional[int] = None,\n    ) -> None:\n\n        self._pruners = []  # type: List[SuccessiveHalvingPruner]\n        self._reduction_factor = reduction_factor\n        self._total_trial_allocation_budget = 0\n\n        if n_brackets is None:\n            # In the original paper http://www.jmlr.org/papers/volume18/16-558/16-558.pdf, the\n            # inputs of Hyperband are `R`: max resource and `\\eta`: reduction factor. The\n            # number of brackets (this is referred as `s_{max} + 1` in the paper) is calculated\n            # by s_{max} + 1 = \\floor{\\log_{\\eta} (R)} + 1 in Algorithm 1 of the original paper.\n            self._n_brackets = (\n                math.floor(math.log2(max_resource) / math.log2(reduction_factor)) + 1\n            )\n        else:\n            message = (\n                \"The argument of `n_brackets` is deprecated. \"\n                \"The number of brackets is automatically determined by `max_resource` and \"\n                \"`reduction_factor` as \"\n                \"`n_brackets = floor(log(max_resource) / log(reduction_factor)) + 1`. \"\n                \"Please specify `reduction_factor` appropriately.\"\n            )\n            warnings.warn(message, DeprecationWarning)\n            _logger.warning(message)\n            self._n_brackets = n_brackets\n\n        self._trial_allocation_budgets = []  # type: List[int]\n\n        _logger.debug(\"Hyperband has {} brackets\".format(self._n_brackets))\n\n        for i in range(self._n_brackets):\n            trial_allocation_budget = self._calculate_trial_allocation_budget(i)\n            self._total_trial_allocation_budget += trial_allocation_budget\n            self._trial_allocation_budgets.append(trial_allocation_budget)\n\n            # N.B. (crcrpar): `min_early_stopping_rate` has the information of `bracket_index`.\n            if min_early_stopping_rate_low is None:\n                min_early_stopping_rate = i\n            else:\n                message = (\n                    \"The argument of `min_early_stopping_rate_low` is deprecated. \"\n                    \"Please specify `min_resource` appropriately.\"\n                )\n                warnings.warn(message, DeprecationWarning)\n                _logger.warning(message)\n                min_early_stopping_rate = min_early_stopping_rate_low + i\n\n            _logger.debug(\n                \"{}th bracket has minimum early stopping rate of {}\".format(\n                    i, min_early_stopping_rate\n                )\n            )\n\n            pruner = SuccessiveHalvingPruner(\n                min_resource=min_resource,\n                reduction_factor=reduction_factor,\n                min_early_stopping_rate=min_early_stopping_rate,\n            )\n            self._pruners.append(pruner)\n\n    def prune(self, study: \"optuna.study.Study\", trial: FrozenTrial) -> bool:\n        i = self._get_bracket_id(study, trial)\n        _logger.debug(\"{}th bracket is selected\".format(i))\n        bracket_study = self._create_bracket_study(study, i)\n        return self._pruners[i].prune(bracket_study, trial)\n\n    def _calculate_trial_allocation_budget(self, pruner_index: int) -> int:\n        \"\"\"Compute the trial allocated budget for a bracket of ``pruner_index``.\n\n        In the `original paper <http://www.jmlr.org/papers/volume18/16-558/16-558.pdf>`, the\n        number of trials per one bracket is referred as ``n`` in Algorithm 1. Since we do not know\n        the total number of trials in the leaning scheme of Optuna, we calculate the ratio of the\n        number of trials here instead.\n        \"\"\"\n\n        s = self._n_brackets - 1 - pruner_index\n        return math.ceil(self._n_brackets * (self._reduction_factor ** s) / (s + 1))\n\n    def _get_bracket_id(self, study: \"optuna.study.Study\", trial: FrozenTrial) -> int:\n        \"\"\"Compute the index of bracket for a trial of ``trial_number``.\n\n        The index of a bracket is noted as :math:`s` in\n        `Hyperband paper <http://www.jmlr.org/papers/volume18/16-558/16-558.pdf>`_.\n        \"\"\"\n\n        n = (\n            hash(\"{}_{}\".format(study.study_name, trial.number))\n            % self._total_trial_allocation_budget\n        )\n        for i in range(self._n_brackets):\n            n -= self._trial_allocation_budgets[i]\n            if n < 0:\n                return i\n\n        assert False, \"This line should be unreachable.\"\n\n    def _create_bracket_study(\n        self, study: \"optuna.study.Study\", bracket_index: int\n    ) -> \"optuna.study.Study\":\n        # This class is assumed to be passed to\n        # `SuccessiveHalvingPruner.prune` in which `get_trials`,\n        # `direction`, and `storage` are used.\n        # But for safety, prohibit the other attributes explicitly.\n        class _BracketStudy(optuna.study.Study):\n\n            _VALID_ATTRS = (\n                \"get_trials\",\n                \"direction\",\n                \"_storage\",\n                \"_study_id\",\n                \"pruner\",\n                \"study_name\",\n                \"_bracket_id\",\n                \"sampler\",\n            )\n\n            def __init__(self, study: \"optuna.study.Study\", bracket_id: int) -> None:\n                super().__init__(\n                    study_name=study.study_name,\n                    storage=study._storage,\n                    sampler=study.sampler,\n                    pruner=study.pruner,\n                )\n                self._bracket_id = bracket_id\n\n            def get_trials(self, deepcopy: bool = True) -> List[FrozenTrial]:\n                trials = super().get_trials(deepcopy=deepcopy)\n                pruner = self.pruner\n                assert isinstance(pruner, HyperbandPruner)\n                return [t for t in trials if pruner._get_bracket_id(self, t) == self._bracket_id]\n\n            def __getattribute__(self, attr_name):  # type: ignore\n                if attr_name not in _BracketStudy._VALID_ATTRS:\n                    raise AttributeError(\n                        \"_BracketStudy does not have attribute of '{}'\".format(attr_name)\n                    )\n                else:\n                    return object.__getattribute__(self, attr_name)\n\n        return _BracketStudy(study, bracket_index)\n", "path": "optuna/pruners/hyperband.py"}]}