はじめに
HyperbandとはBanditの考え方を利用して早期打ち切りと適応的な計算資源割当を組み込んだ画期的なRandom Searchです．先行研究としてはSuccessive Halvingが存在し，この手法は適応的な計算資源割当を行いません．参照にしたコードはこちら．
以下，変数設定の集合を $\mathcal{T}$, その計算資源量を $t$ とします．
論文にも書いてある通り，$t$ に対して割り当てる計算資源を多くすれば，実際に評価できる $t$ の数は少なくなりす．逆に割り当てる計算資源を少なくすると評価できる $t$ の数は多くなるものの，計算効率が落ちます．例えば，学習が非常に遅く終盤にならないと性能がはっきりしないモデルに対しては評価数を多くしても効率的とは言えないです．また，比較的序盤に性能差が明らかになるようなモデルであれば，前半から打ち切ったとしても探索性能は落ちることはありません．このバランスをBanditの考え方を利用して解決しようという手法．
アルゴリズム
変数
論文では $n$ と $r$ は探索上のTrade-offになっているが，Successive Halvingではこの2つの変数が固定されていて頑健性に欠けていると言っています．ちなみに論文では各 $i$ に対して，$t$ の評価を最初からやり直すような実装になっていますが，多くの実装では評価計算を途中から継続しているようです．そのため，この記事においても同様に計算を途中から継続するという方針で解説を進めます．
| 変数名 | 役割 | 具体例 |
|---|---|---|
| $R$ | 1つの変数設定 $t$ の評価が要する最大の計算回数． | 深層学習のエポック数 |
| $r$ | ある反復時に1つの変数設定の評価に用いる計算資源量 | 本来200エポックの学習を$r$ エポックで打ち切る． |
| $n$ | ある反復時に評価する変数設定の数． | 実質的には手元にあるGPUの個数． |
| $\eta$ | 1反復修了時に打ち切る変数設定の割合．全体の$1 / \eta$ が打ち切られる． | 役割の通り． |
| $B$ | 全体の計算回数． | スパコン借りている場合はスパコンにかかる費用． |
| $T$ | 現在評価している変数設定の集合 | 役割の通り． |
| $t$ | $T$ の要素 | 役割の通り． |
| $s_{max}$ | $R$ を $\eta$ で何回割れるか．（何回打ち切り操作をはさむか．） | $R=81 = 3^4$ なら 3で4回割っても0にならない． |
なお，$T$ は $\mathcal{T}$ からサンプルされるという関係上，$t \in T \subset \mathcal{T}$ となります．
関数の意味
・1,2行目はHyperbandに特有な部分．評価する変数設定と評価時間のバランスを取っている．
・3-9行目はSuccessive Halvingのアルゴリズム
・get_hyperparameter_configuration(n)
ランダムに得られた $n$ 個の異なる $t \in \mathcal{T}$ を返す関数．また，$n$ 個の $t$ の集合は $T \subset \mathcal{T}$ と定義されている．
・run_then_return_val_loss(t, r)
上の関数で得られた集合 $T$ の各要素 $t$ に対して，$r$ の計算資源を割り当てて，Validation Loss（最適化対象）の計算を継続する．
・top_k(configs, losses, k)
上で評価していた変数設定 $t$ の内，上位 $k$ 個を選択し，再度，集合 $T$ を構築する．
具体例
例えば，上のような学習曲線を描くような学習モデルがあるします．実際に $\eta = 2, R = 16$ としてHyperbandを利用してみましょう．
$s_{max} = log_2 R = 4$ なので，$s=0,1,2,3,4$に対して実行することになります．
以下の表では全て，横軸がエポック数で縦軸が異なる変数設定を指します．それぞれの変数設定は独立した計算機によって計算されていると考えてください．黄色に塗られている部分が実際にHyperbandが評価する部分になります．また，色が変化する部分で枝刈りが行われたと考えてください．色が塗られていない部分は実際の値ですが，評価されていないです．
s = 4
枝刈りするたびに $n$ は16, 8, 4, 2, 1 と推移します．また，$r$ は 1, 2, 4, 8, 16 と推移します．
総計算量は48エポックです．最終的に得られた最高値は0.50です．実際の最高値0.67を取りこぼしてしまいました．
s = 3
枝刈りするたびに $n$ は10, 5, 2, 1 と推移します．また，$r$ は 2, 4, 8, 16 と推移します．
総計算量は46エポックです．最終的に得られた最高値は0.50です．実際の最高値0.64を取りこぼしてしまいました．
s = 2
枝刈りするたびに $n$ は 7, 3, 1 と推移します．また，$r$ は 4, 8, 16 と推移します．
総計算量は48エポックです．最終的に得られた最高値は0.50です．実際の最高値0.64を取りこぼしてしまいました．
s = 1
枝刈りするたびに $n$ は 5, 2 と推移します．また，$r$ は 8, 16 と推移します．
総計算量は56エポックです．最終的に得られた最高値は0.64です．実際の最高値0.64をしっかりと得ることができました．
s = 0
$n$ と $r$ は 5, 16 で固定です．
総計算量は80エポックです．全てを予算最大で計算しているので当然最高の値を得ることができます．
全体の結果
上記の通り，$s$ があまりに大きいと後々成長してくるような変数設定を切ってしまうことになりますね．この結果を見れば，計算資源量と探索数のTrade-offを理解していただけると思います．今回の場合は $s=1$ が最適であるということになります．それより大きい値を取ると，軒並み早期打ち切りで首が切られてしまいます．また，$s$ を小さくすると余分な計算をすることになります．よって，事前にモデルの性質がわからない場合はHyperbandでは計算量をなるべく抑えつつ，良い変数設定を見つけることができるようなバランスの良い$s$ とそうでない $s$ も満遍なく利用することができます．愚直ではありますが，ブラックボックス関数では有効な手法だと思います． また，論文中にもあるとおり，途中である $s$ が良さそうだと思ったときであってもリグレットを押さえるために，毎回 $s$ は変化させるべきだとも言っています．
今回は成長率が設定によって大きく異なる目的関数を利用したため，$s$ をなるべく大きめに取ることが良いということがわかりましたが，実際には下の図のように最初の順位が最後まで変わらないような目的関数も存在するため $s$ を小さくして最初から枝刈りする方が良い場合もあります．結局，それのバランスを取れるように満遍なく探索しましょう，ということが論文の主旨だと思います．
補足
Massively Parallel Hyperparameter Tuning
Parallelizing Hyperband for Large-Scale Tuning
A simple transfer-learning extension of Hyperband
BOHB: Robust and Efficient Hyperparameter Optimization at Scale