AI Labの阿部です．

つい最近Preferred Networks社から機械学習のハイパーパラメータ最適化フレームワークOptunaが公開されたこともあってハイパーパラメータ最適化が注目を集めていますね！

機械学習のハイパーパラメータ最適化の代表的な手法といえば，TPE[Bergstra et al., 2011]，SMAC[Hutter et al. 2011]，Hyperband[Li et al., 2018]などが挙げられます．

今回は，HyperbandのアルゴリズムのベースとなっているSuccessive Halving[Jamieson et al., 2015]という手法について解説してみたいと思います．

Successive Halving

Successive Halvingはハイパーパラメータ最適化を多腕バンディット問題の最適腕識別として考え，より良いハイパーパラメータほど多くの学習時間を割り当てる手法です．

現在，ハイパーパラメータ最適化では
1. 候補となるハイパーパラメータをサンプルする
2. そのハイパーパラメータを実際に用いて学習をさせてみる
3. 学習後のモデルを評価する¹

という流れを繰り返すことが一般的となっています．しかし，モデルを1回学習させるためには多くの時間がかかるため，サンプルしたハイパーパラメータの分だけ学習を実行しなければいけないとなると，非常に多くの実行時間が必要になってしまいます．

そこで，Successive Halvingでは，
1. 候補となるハイパーパラメータに対して学習を途中まで進める
2. その段階で評価値が悪いハイパーパラメータの下位半分を候補から削除する
3. 残ったハイパーパラメータに対して学習を継続する
という流れを繰り返します．これによって，評価値が悪そうなハイパーパラメータに関しては学習を早期で打ち切ることができ，余計な学習を行わないで評価値が良さそうなハイパーパラメータにだけ多くの学習時間を割り当てることができるため，実行時間的に効率が良くなることが期待されます．

アルゴリズム

Successive Halvingの具体的なアルゴリズムは，以下のようになっています．

Budget \(B\)は，総学習時間に当たり，例えば総epoch数やバッチ更新を行う総回数を指定します．つまり，Successive Halvingでは，学習を実行できる総時間が決まっていて，その時間を各ハイパーパラメータに対して割り当てる，ということを行っています．

また，\(l_{i,k}\)は，\(i\)番目のハイパーパラメータに対する学習を\(k\) iteration分だけ進めたときの評価値を表しています．

\(n\)個のハイパーパラメータの候補の生成方法は明確には指定されていませんが，例えば，ハイパーパラメータの空間から一様ランダムに\(n\)個サンプルする，という方法を取ることが多いです．

多くのハイパーパラメータ最適化手法では「評価値が良さそうなところに新たなハイパーパラメータの候補をサンプルする」ということを行いますが，Successive Halvingでは「サンプルされたハイパーパラメータの候補に対してBudgetをいかに割り振るか」ということに焦点を当てているのが特徴的な部分です．

性能解析

Successive Halvingは「Budget \(B\)とサンプルするハイパーパラメータの候補の数\(n\)を増加させると，出力されるハイパーパラメータは最適なハイパーパラメータに漸近的に近づく」ということが理論的に証明されています．

ここからは，その証明の解説を行ってみます．

証明のための準備と仮定

まず，\(\lim_{k\to \infty}l_{i,k}\)が存在して，その値が\(v_i=\lim_{k\to \infty}l_{i,k}\)となるという仮定を起きます．この仮定は，\(l_{i,k}\)が必ず何かしらの値へと収束するということを表しています．証明を簡単に行うために，順序関係を\(v_1\leq \cdots \leq v_n\)としておきましょう．

ハイパーパラメータの空間上で評価値の収束値が最小となるようなハイパーパラメータを\(x_{\ast}\)とし，そのハイパーパラメータに対する評価値の収束値を\(v_{\ast}\)とします．
\(n\)個のハイパーパラメータは確率的にサンプルされるものであるため，この中に最適なハイパーパラメータが含まれていない可能性もあります．ですので，\(v_{\ast}\leq v_1\)となることには注意が必要です．

確率的にサンプルされるハイパーパラメータの候補によって\(v_i\)が決定されるため，\(v_i\)は確率変数となります．ここでは，\(v_i\)が従う累積分布関数を\(F\)とし，以下のように定義します．
$$
P(v_i-v_{\ast}\leq \epsilon)=F(v_{\ast}+\epsilon)
$$また，この逆関数を\(F^{-1}(y)=\sup_x\{x: F(x)\leq y\}\)と定義します．

最適腕識別として証明を行うため，以降では\(n\)個のハイパーパラメータの候補を\(x_i\)とし，\(x_i\)のインデックス\(i\)をアームと呼ぶことにします．したがって，\(l_{i,k}\)や\(v_i\)は\(x_i\)の評価値を表しています．

最後に，\(l_{i,j}\)の値は，単調減少関数\(\gamma:\mathbb{N}\to \mathbb{R}\)を用いて以下のように抑えられると仮定を起きます．
$$
\max_i |l_{i,j}-v_i|\leq \gamma (j), ~\forall j\in \mathbb{N}
$$この仮定は，iterationが増加するにつれて\(l_{i,j}\)が\(v_i\)へと近づいていくことを意味します．この逆関数を\(\gamma^{-1}(y)=\min\{j\in \mathbb{N}: \gamma(j) \leq y\}\)と定義しておきましょう．

命題

\(\delta\in(0,1), \epsilon \geq 4\left(F^{-1}\left(\frac{\log(2/\delta)}{n}\right)-v_{\ast}\right),B=4\lceil\log_2(n)\rceil H(F,\gamma, n, \delta, \epsilon)\)とする． ただし，\(H(F,\gamma,n,\delta,\epsilon) = 2n \int_{v_{\ast}+\epsilon/4}^{\infty} \gamma^{-1}\left(\frac{t-v_{\ast}}{4}\right)dF(t) + \left(\frac{4}{3}\log(2/\delta) + 2nF(v_{\ast} + \epsilon/4)\right) \gamma^{-1} \left(\frac{\epsilon}{16}\right)\)である．

この時，Successive Halvingは確率\(1-\delta\)以上で\(v_{\hat{i}}-v_{\ast}\leq \left(F^{-1}\left(\frac{\log(2/\delta)}{n}\right)-v_{\ast}\right)+\epsilon/2\)を満たすアーム\(\hat{i}\)を出力する．

証明の流れ

証明には，以下の２つの定理が必要になります．
まずは２つの定理の証明をそれぞれ行い，最後にそれらをまとめることで命題の証明を行います．

定理1

任意の\(\epsilon>0\)に対して，
$$
z_{SH} = 2\lceil \log_2(n) \rceil \max_{i=2, \cdots, n} i\left(1 + \gamma^{-1}\left(\max \left \{ \frac{\epsilon}{4}, \frac{v_i – v_1}{2} \right \} \right)\right)
$$と定義する．
この時，Budgetが\(B > z_{SH}\)を満たす場合，Successive Halvingは\(v_{\hat{i}}-v_1 \leq \epsilon/2\)を満たすアーム\(\hat{i}\)を出力する．

直感的解釈

定理1は，「\(n\)個の中で最も良いアーム（\(v_1\)）にどれだけ近いアームを出力することができるか」，ということを表していると解釈することができます．\(\epsilon\)を\(0\)へと近づけることで，一定以上のBudgetを与えることで一番良いアームに限りなく近いアームを選ぶことができるということが，この結果からわかります．つまり，Successive Halvingは一定以上のBudgetがあれば，与えられた\(n\)個のアームの中で最も良いアームを識別することができます．

定理2

\(\delta\in(0,1), p_n=\frac{\log(2/\delta)}{n}\)，\(\epsilon \geq 4(F^{-1}(p_n)-v_{\ast})\)とする．
この時，確率\(1-\delta\)以上で
$$
v_1 \leq F^{-1}(p_n),~ \sum_{i=1}^n \gamma^{-1} \left(\max\left\{\frac{\epsilon}{4}, \frac{v_i-v_1}{2}\right\}\right) \leq H(F,\gamma,n,\delta,\epsilon)
$$が成り立つ．

直感的解釈

定理2は「候補となるアームの数\(n\)を増やしたときに，\(n\)個の中で最も良いアーム（\(v_1\)）が真に最良のアーム（\(v_{\ast}\)）に近づくか」，ということを表していると解釈することができます．実は，定理2はSuccessive Halvingのアルゴリズムにはほぼ関係しておらず，\(n\)個のアームのサンプル方法に対しての定理になっています．\(n\)を無限大へと近づけることで，\(v_1\)が限りなく\(v_{\ast}\)へと近づくことがわかります．無限個のアームをサンプルすれば，その中に最適なアームに限りなく近いものが含まれるというのは直感的だと思います．

定理1の証明

証明は，反復\(k\)において最適なアーム\(1\)が集合から削除される事象，すなわち，\(\{ 1\in S_k, 1\not\in S_{k+1}\}\)について考えることで行います．より具体的には，「\(\{ 1\not\in S_{k+1}\}\)となったとき，\(S_{k+1}\)内に含まれる全てのアームは\(v_i-v_1\leq \epsilon/2\)を満たす」ということを証明していきます．

事象\(\{ 1\in S_k, 1\not\in S_{k+1}\}\)は，\(1\)以外のアームが上位\(\lceil|S_k|/2\rceil\)を占めているときに起こるので，
$$
\{ 1\in S_k, 1\not\in S_{k+1}\} \Leftrightarrow \left\{ \sum_{i\in S_k} \mathbb{1} \{l_{i,R_k} < l_{1,R_k} \} \geq \lceil |S_k|/2 \rceil\right\} \tag{A}
$$が成り立ちます．

また，\(\gamma\)の定義より，全ての\(j\)に対して\(\max_i|l_{i,j}-v_i| \leq \gamma(j)\)が成り立つので，\(t \geq \tau_i = \gamma^{-1}\left(\frac{v_i -v_1}{2}\right)\)のもとで，\(|l_{i,t} – v_i| \leq \gamma(t) \leq \frac{v_i – v_1}{2}\)となります．よって，
$$
\begin{eqnarray}
l_{i,t} – l_{1,t} &=& l_{i,t} – v_i + v_i – v_1 + v_1 – l_{1,t} \\
&=& l_{i,t} – v_i – (l_{1,t} – v_1) + v_i – v_1 \\
&\geq& -2\gamma(t) + v_i – v_1 \\
&\geq& -2\frac{v_i – v_1}{2} + v_i – v_1 \\
&=& 0
\end{eqnarray}
$$を得るので，\(t \geq \tau_i \Rightarrow l_{i,t} – l_{1,t} \geq 0\)が成り立ちます．

したがって，
$$
l_{i,t} < l_{1,t} \Rightarrow t < \tau_i
$$が成り立つことを導けます．よって，(A)式は
$$
(A) \Rightarrow \left\{ \sum_{i\in S_k} \mathbb{1} \{R_k < \tau_i \} \geq \lceil |S_k|/2 \rceil\right\}
$$となります．さらに，\(i<j\)の時，\(\tau_i \geq
\tau_j\)が成り立つので，
$$
\begin{eqnarray}
(A) &\Rightarrow& \left\{ \sum_{i=1}^{\lceil|S_k|/2\rceil} \mathbb{1} \{R_k < \tau_i \} \geq \lceil |S_k|/2 \rceil\right\} \\
&\Leftrightarrow& \left\{ R_k < \tau_{\lceil|S_k|/2\rceil} \right\}
\end{eqnarray}
$$が成り立ちます．したがって，\(R_k \geq \tau_{\lceil|S_k|/2\rceil} \Rightarrow \{ 1 \not\in S_k \lor 1\in S_{k+1}\}\)が導けます．これを用いると，
$$
\begin{eqnarray}
\{ 1\in S_k, R_k \geq \tau_{\lceil|S_k|/2\rceil}\}
&\Rightarrow& \{ (1\in S_k, 1\not\in S_k) \lor (1\in S_k, 1\in S_{k+1}) \} \\
&\Rightarrow& \{ 1\in S_k, 1\in S_{k+1}\} \\
&\Rightarrow& \{ 1\in S_{k+1}\} \tag{B}
\end{eqnarray}
$$が成り立ちます．

また，\(B>z_{SH}\)であることを用いると，
$$
\begin{eqnarray}
R_k \geq r_k &=& \lfloor \frac{B}{|S_k|\lceil\log_2(n)\rceil} \rfloor\\
&\geq& \frac{B}{|S_k|\lceil\log_2(n)\rceil} – 1 \\
&\geq& \frac{2}{|S_k|} \max_{i=2, \cdots, n} i\left(1 + \gamma^{-1}\left(\max \left\{\frac{\epsilon}{4}, \frac{v_i – v_1}{2}\right\}\right)\right) – 1 \\
&\geq& \frac{2}{|S_k|} (\lceil|S_k|/2\rceil)\left(1 + \gamma^{-1}\left(\max \left\{\frac{\epsilon}{4}, \frac{v_{\lceil|S_k|/2\rceil} – v_1}{2}\right\}\right)\right) – 1\\
&\geq& \left(1 + \gamma^{-1}\left(\max \left\{\frac{\epsilon}{4}, \frac{v_{\lceil|S_k|/2\rceil} – v_1}{2}\right\}\right)\right) – 1\\
&=& \gamma^{-1}\left(\max \left\{\frac{\epsilon}{4}, \frac{v_{\lceil|S_k|/2\rceil} – v_1}{2}\right\}\right) \tag{C}
\end{eqnarray}
$$を導くことができます．

ここからは，(B)式と(C)式を用いて，「\(\{ 1\not\in S_{k+1}\}\)となったとき，\(S_{k+1}\)内に含まれる全てのアームは\(v_i-v_1\leq \epsilon/2\)を満たす」ということを証明していきます．

(C)式には\(\max\)演算が入っていて複雑なため，反復\(k\)における事象を\(\left\{\frac{v_{\lceil|S_k|/2\rceil}-v_1}{2}\geq \frac{\epsilon}{4}, 1\in S_k\right\}\)のとき，\(\left\{\frac{v_{\lceil|S_k|/2\rceil}-v_1}{2} < \frac{\epsilon}{4}, 1\in S_k\right\}\)のとき，\(\{1\not\in S_k\}\)のときの３つのcaseに分割し，それぞれについて考えていきましょう．

case 1: \(\left\{\frac{v_{\lceil|S_k|/2\rceil}-v_1}{2}\geq \frac{\epsilon}{4}, 1\in S_k\right\}\)

(C)式より，\(R_k \geq \gamma^{-1}\left(\frac{v_{\lceil|S_k|/2\rceil} – v_1}{2}\right) = \tau_{\lceil|S_k|/2\rceil}\)となります．したがって，(B)式の条件を満たすため，\(\{1\in S_{k+1}\}\)が成り立つことがわかります．よってこのcaseでは，アーム\(1\)は次の反復\(k+1\)の集合\(S_{k+1}\)内に含まれることになります．

case 2: \(\left\{\frac{v_{\lceil|S_k|/2\rceil}-v_1}{2} < \frac{\epsilon}{4}, 1\in S_k\right\}\)

(C)式より，\(R_k \geq \gamma^{-1}\left(\frac{\epsilon}{4}\right)\)となります．\(\gamma^{-1}\left(\frac{\epsilon}{4}\right) < \tau_{\lceil|S_k|/2\rceil}\)となることを考えると，このcaseでは，\(1\in S_{k+1}\)となる場合と\(1\not\in S_{k+1}\)となる場合が考えられます．

重要なのはアーム\(1\)以外のアームが出力されるときの\(v_{\hat{i}}\)の値ですので²，最初は\(1 \not\in S_{k+1}\)となる場合を考えましょう．
\(p=\min \{i \in [n] ~|~ \frac{v_i – v_1}{2} \geq \frac{\epsilon}{4} \}\)と置くと，\(p\)の定義より，
$$
R_k \geq \gamma^{-1}\left(\frac{\epsilon}{4}\right) \geq \gamma^{-1}\left(\frac{v_i – v_1}{2}\right) = \tau_i,~ \forall_i \geq p
$$が成り立ちます．このことと，先ほど示した\(t\geq \tau_i \Rightarrow l_{i,t} \geq l_{1,t}\)を用いると，\(i\geq p\)を満たすアーム\(i\)に対して\(l_{i, R_k} \geq l_{1, R_k}\)が成り立ちます．したがって，\(i\geq p\)を満たすアームはアーム\(1\)より早い反復，あるいは同じ反復で削除されることがわかります．さらに，\(p> \lceil|S_k|/2\rceil
\)が成り立つことを考えると，\(i\geq p\)を満たすアーム\(i\)は全て削除されることがわかります．したがって，次反復\(k+1\)における集合\(S_{k+1}\)内のアーム\(i\)は全て\(\frac{v_i-v_1}{2}<\frac{\epsilon}{4}\)を満たすことになります．

したがって，\(\{1\in S_{k}, 1\not\in S_{k+1}\}\Rightarrow \max_{i\in S_{k+1}} v_i \leq v_1 + \frac{\epsilon}{2}\)が成り立ち，この後最終的にSuccessive Halvingが出力するアーム\(\hat{i}\)は最低でも\(v_{\hat{i}} \leq v_1 + \frac{\epsilon}{2}\)を満たすということが導けます．

一方，\(1 \in S_{k+1}\)となる場合では，次反復\(k+1\)でcase 1またはcase 2のどちらかを必ず満たすことになります．したがって，この場合も最終的にはアーム\(\hat{i}=1\)または\(v_{\hat{i}} \leq v_1 + \frac{\epsilon}{2}\)を満たすアームを出力することになります．

case 3: \(\{1\not\in S_k\}\)

このcaseでは，すでにアーム\(1\)が削除されてしまっているという状況を前提にしています．

最初の反復の集合\(S_0\)内にアーム\(1\)は必ず含まれていたはずなので，反復\(k\)より前のどこかの反復\(r<k\)でアーム\(1\)が削除されたという事象，つまり\(\{1\in S_r, 1\not\in S_{r+1}\}\)が起こっていたはずです．これまでに示したように，case 1においては必ず\(1 \in S_{r+1}\)となるため，結局アーム\(1\)が削除されるのはcase 2の場合においてのみということになります．

したがって，case 3では集合内のアームは\(\max_{i\in S_{k}} v_i \leq v_1 + \frac{\epsilon}{2}\)を満たしているはずなので，この場合も最終的には\(v_{\hat{i}} \leq v_1 + \frac{\epsilon}{2}\)を満たすアームを出力することになります．

定理1まとめ

case 1からcase 3までの結果をまとめると，\(v_{\hat{i}} \leq v_1 + \frac{\epsilon}{2}\)を満たすアーム\(\hat{i}\)を出力することが導くことができます．

これで定理1を証明することができました．次は定理2の証明を行いましょう．

定理2の証明

みやすさのため，\(M=\gamma^{-1}\left(\frac{\epsilon}{16}\right), \mu=\mathbb{E}[\min\left\{M, \gamma^{-1}\left(\frac{v_1-v_{\ast}}{4}\right)\right\}]\)と置きましょう．また，事象\(\xi_1, \xi_2\)を
$$
\begin{eqnarray}
\xi_1 &=& \{v_1 \leq F^{-1}(p_n)\}\\
\xi_2 &=& \left\{\sum_{i=1}^n \min\left\{M, \gamma^{-1}\left(\frac{v_i-v_{\ast}}{4}\right)\right\} \leq n\mu + \sqrt{2n\mu M\log(2/\delta)} + \frac{2}{3}M\log(2/\delta)\right\}
\end{eqnarray}
$$と定義しておきます．

定理2の証明は，まず\(\xi_1, \xi_2\)が確率\(1-\delta\)以上で成り立つことを示し，その後に\(\xi_1, \xi_2\)が成り立つ場合に\(\sum_{i=1}^n \gamma^{-1} \left(\max\left\{\frac{\epsilon}{4}, \frac{v_i-v_1}{2}\right\}\right) \leq H(F,\gamma,n,\delta,\epsilon)\)が成り立つことを示すことで行います．

ではまず，\(\xi_1, \xi_2\)が確率\(1-\delta\)以上で成り立つことを示しましょう．
事象\(\xi_1\)について，\(p(\xi_1^c) = p(\min_{i=1,\cdots,n} v_i > F^{-1}(p_n)) = (1 – p_n)^n \leq \exp(-np_n) \leq \frac{\delta}{2}\)が成り立ちます．また，
$$
\mathbb{E}\left[\min\left\{M, \gamma^{-1}\left(\frac{v_i-v_{\ast}}{4}\right)\right\}^2\right] \leq \mathbb{E}\left[M \min\left\{M, \gamma^{-1}\left(\frac{v_i-v_{\ast}}{4}\right)\right\}\right] = M\mu
$$より，Bernsteinの不等式を用いると，\(p(\xi_2^c) \leq \frac{\delta}{2}\)を導くことができます．³

したがって，\(p(\xi_1 \land \xi_2) \geq \left(1 – \frac{\delta}{2}\right)^2 = 1-\delta+\frac{\delta^2}{4} \geq 1 – \delta\)となり，確率\(1-\delta\)以上で事象\(\xi_1,\xi_2\)が成立することが導けます．

次に，\(\xi_1,\xi_2\)が成り立つときに，\(\sum_{i=1}^n \gamma^{-1} (\max\left\{\frac{\epsilon}{4}, \frac{v_i-v_1}{2}\right\}) \leq H(F,\gamma,n,\delta,\epsilon)\)が成り立つことを示しましょう．

このために，まず，\(\max\left\{\frac{\epsilon}{4}, \frac{v_i-v_1}{2}\} \geq \min\{\frac{\epsilon}{4}, \frac{v_i-v_{\ast}}{4}\right\}\)が成り立つことを示します．\(\max\)演算が入っているので，ここでも場合分けをすることで考えます．

case 1: \(\frac{\epsilon}{4} \leq \frac{v_i-v_1}{2}\)

事象\(\xi_1\)より，\(v_{\ast} \leq v_1 \leq F^{-1}(p_n)\)なので，
$$
\frac{v_i-v_1}{2} \geq \frac{v_i – v_{\ast} + v_{\ast} – F^{-1}(p_n)}{2} = \frac{v_i – v_{\ast}}{4} + \frac{v_i – v_{\ast}}{4} – \frac{F^{-1}(p_n) – v_{\ast}}{2} \geq \frac{v_i – v_{\ast}}{4} + \frac{v_i – v_1}{4} – \frac{F^{-1}(p_n) – v_{\ast}}{2}
$$が成り立ちます．また，仮定\(\epsilon \geq 4(F^{-1}(p_n) – v_{\ast})\)と，case 1における仮定\(\frac{\epsilon}{4} \leq \frac{v_i – v_1}{2}\)を用いると，\(\frac{v_i – v_{\ast}}{4} + \frac{v_i – v_1}{4} – \frac{F^{-1}(p_n) – v_{\ast}}{2} \geq \frac{v_i – v_{\ast}}{4}\)となります．

よって，\(\frac{v_i – v_1}{2} \geq \frac{v_i – v_{\ast}}{4}\)が成り立つことが示せました．

case 2: \(\frac{\epsilon}{4} > \frac{v_i-v_1}{2}\)

case 2の仮定を用いると，
$$
\frac{v_i-v_{\ast}}{4} = \frac{v_i – v_1}{4} + \frac{v_1 – v_{\ast}}{4} < \frac{\epsilon}{8} + \frac{v_1 – v_{\ast}}{4}
$$が成り立ちます．

さらに，事象\(\xi_1\)より，\(v_{\ast} \leq v_1 \leq F^{-1}(p_n)\)なので，\(\frac{\epsilon}{8} + \frac{v_1 – v_{\ast}}{4} \leq \frac{\epsilon}{8} + \frac{F^{-1}(p_n) – v_{\ast}}{4}\)が導けます．

最後に，\(\epsilon \geq 4(F^{-1}(p_n) – v_{\ast})\)を用いると，\(\frac{\epsilon}{8} + \frac{F^{-1}(p_n) – v_{\ast}}{4} < \frac{\epsilon}{4}\)が成り立つことが示せました．

定理2まとめ

case 1とcase 2の結果から，\(\max\left\{\frac{\epsilon}{4}, \frac{v_i-v_1}{2}\right\} \geq \min\left\{\frac{\epsilon}{4}, \frac{v_i-v_{\ast}}{4}\right\}\)が成り立つことが示せました．
このことと\(\xi_1, \xi_2\)の定義を用いると，事象\(\xi_1,\xi_2\)が成り立つ時，
$$
\begin{eqnarray}
\sum_{i=1}^n \gamma^{-1}\left(\max\left\{\frac{\epsilon}{4},\frac{v_i-v_1}{2}\right\}\right) &\leq& \sum_{i=1}^n \gamma^{-1}\left(\max\left\{\frac{\epsilon}{4},\frac{v_i-v_{\ast}}{4}\right\}\right)\\
&\leq& \sum_{i=1}^n \gamma^{-1}\left(\max\left\{\frac{\epsilon}{16},\frac{v_i-v_{\ast}}{4}\right\}\right)\\
&=& \sum_{i=1}^n \min\left\{M,\gamma^{-1}\left(\frac{v_i-v_{\ast}}{4}\right)\right\}\\
&\leq& n\mu + \sqrt{2n\mu M\log(2/\delta)} + \frac{2}{3}M\log(2/\delta)\\
&\leq& \left(\sqrt{n\mu} + \sqrt{\frac{2}{3}M\log(2/\delta)}\right)^2\\
&\leq& 2n\mu + \frac{4}{3}M\log(2/\delta)
\end{eqnarray}
$$が成り立つことがわかります．

\(\mu\)を展開すると，
$$
\begin{eqnarray}
\mu &=& \mathbb{E}\left[\min\left\{M, \gamma^{-1}(\frac{v_i-v_{\ast}}{4})\right\}\right]\\
&=& \mathbb{E}\left[\left(\gamma^{-1}(\max\left\{\frac{\epsilon}{16},\frac{v_i-v_{\ast}}{4}\right\}\right)\right]\\
&=&\int_{-\infty}^{v_{\ast}+\epsilon/4}\gamma^{-1}\left(\frac{\epsilon}{16}\right)dF(t) + \int_{v_{\ast}+\epsilon/4}^{\infty}\gamma^{-1}\left(\frac{t-v_{\ast}}{4}\right)dF(t)\\
&=&\gamma^{-1}\left(\frac{\epsilon}{16}\right)F(v_{\ast}+\epsilon/4) + \int_{v_{\ast}+\epsilon/4}^{\infty}\gamma^{-1}\left(\frac{t-v_{\ast}}{4}\right)dF(t)
\end{eqnarray}
$$となるので，これを代入すると，事象\(\xi_1,\xi_2\)が成り立つ時，
$$
\begin{eqnarray}
\sum_{i=1}^n \gamma^{-1}\left(\max\left\{\frac{\epsilon}{4},\frac{v_i-v_1}{2}\right\}\right) &\leq& 2n\mu + \frac{4}{3}M\log(2\delta)\\
&=& 2n \int_{v_{\ast}+\epsilon/4}^{\infty} \gamma^{-1}\left(\frac{t-v_{\ast}}{4}\right)dF(t) + \left(\frac{4}{3}\log(2/\delta) + 2nF(v_{\ast} + \epsilon/4)\right) \gamma^{-1} \left(\frac{\epsilon}{16}\right)
\end{eqnarray}
$$が成り立つことが導けます．

この結果と，事象\(\xi_1,\xi_2\)が確率\(1-\delta\)以上で成り立つことを考えると，確率\(1-\delta\)以上で
$$
v_1 \leq F^{-1}(p_n),~ \sum_{i=1}^n \gamma^{-1} \left(\max\left\{\frac{\epsilon}{4}, \frac{v_i-v_1}{2}\right\}\right) \leq H(F,\gamma,n,\delta,\epsilon)
$$が成り立つことがわかります．

これで定理1と定理2の証明が終わりました．最後に，定理1と定理2の結果をまとめることで，命題の証明を行いましょう．

命題の証明

\(\epsilon \geq 4\left(F^{-1}\left(\frac{\log(2/\delta)}{n}\right)-v_{\ast}\right)\)より，定理2から確率\(1-\delta\)以上で
$$
\sum_{i=1}^n \gamma^{-1} \left(\max\left\{\frac{\epsilon}{4}, \frac{v_i-v_1}{2}\right\}\right) \leq H(F,\gamma,n,\delta,\epsilon)
$$が成り立ちます．また，\(\gamma^{-1}(x)\)が\(x\)に関して単調減少であることを用いると，
$$
\begin{eqnarray}
z_{SH} &=& 2\lceil \log_2(n) \rceil \max_{i=2, \cdots, n} i\left(1 + \gamma^{-1}\left(\max \left\{\frac{\epsilon}{4}, \frac{v_i – v_1}{2}\right\}\right)\right)\\
&\leq& 2\lceil \log_2(n) \rceil \left(\max_{i=2, \cdots, n} i + \max_{i=2, \cdots, n} i\left(\gamma^{-1}\left(\max \left\{\frac{\epsilon}{4}, \frac{v_i – v_1}{2}\right\}\right)\right)\right)\\
&\leq& 2\lceil \log_2(n) \rceil \left(n + \max_{i=2, \cdots, n} i\left(\gamma^{-1}\left(\max \left\{\frac{\epsilon}{4}, \frac{v_i – v_1}{2}\right\}\right)\right)\right)\\
&\leq& 2\lceil \log_2(n) \rceil \left(n + \sum_{i=1,\cdots,n}\gamma^{-1}\left(\max \left\{\frac{\epsilon}{4}, \frac{v_i – v_1}{2}\right\}\right)\right)
\end{eqnarray}
$$が成り立ちます．よって，
$$
\begin{eqnarray}
z_{SH} &\leq& 2\lceil \log_2(n) \rceil \left(n + \sum_{i=1,\cdots,n}\gamma^{-1}\left(\max \left\{\frac{\epsilon}{4}, \frac{v_i – v_1}{2}\right\}\right)\right)\\
&\leq& 2\lceil \log_2(n) \rceil \left(n + H(F,\gamma,n,\delta,\epsilon)\right)\\
&<& 4\lceil \log_2(n) \rceil H(F,\gamma,n,\delta,\epsilon)=B
\end{eqnarray}
$$が成り立つので，\(B>z_{SH}\)を満たします．
したがって定理1の前提条件を満たすので，\(v_{\hat{i}}-v_1\leq \epsilon/2\)が成り立ちます．
また，定理2から\(v_{\ast}\leq v_1\leq v_{\ast}+(F^{-1}(p_n)-v_{\ast})\)が同時に成り立つことがわかるので，
$$
v_{\hat{i}}-v_1 \leq v_{\hat{i}}-v_{\ast}\leq (F^{-1}(p_n)-v_{\ast})+\epsilon /2
$$も成り立つことが導けます．

これらの結果を組み合わせると，Successive Halvingは確率\(1-\delta\)以上で\(v_{\hat{i}}-v_{\ast}\leq \left(F^{-1}\left(\frac{\log(2/\delta)}{n}\right)-v_{\ast}\right)+\epsilon/2\)を満たすアーム\(\hat{i}\)を出力することを示せました．

直感的解釈

定理1では「一定以上のBudgetを与えることでアーム\(1\)に限りなく近いアームを選ぶことができる」ということが，定理2では「\(n\)を無限大へと近づけることで，\(v_1\)が限りなく\(v_{\ast}\)へと近づく」ということがわかります．

これら２つの定理をあわせて証明した命題は単にこれらの結果を合わせたような結果となっているだけですので，直感的には，「\(n\)と\(B\)を無限大へと近づけると，Successive Halvingは最適なアームを出力する」というイメージを持つことができます．当たり前といえば当たり前なのですが，理論的に保証がされているとアルゴリズムを使用する際に安心できるので，意外と重要なことなのかな，と思います．

Hyperbandとのつながり

Successive Halvingは強力な理論保証を持つアルゴリズムですが，実際のハイパーパラメータ最適化では\(\gamma\)や\(F\)はわからないことが一般的なため，\(B\)や\(n\)をどれくらいに設定すればいいかは事前にわからないことがほとんどです．

\(B\)と\(n\)はトレードオフの関係にあります．\(n\)を増加させると多くのアームを候補とすることができますが，その分だけ\(B\)を増加させないと各アームに対して十分に学習を進めることができません．一方で，\(n\)を減少させると各アームに対してより多くの学習時間を割り当てることができますが，その中に最適なアームに近いものが含まれている可能性も低くなってしまいます．

Hyperbandはこの問題に対処した手法であり，\(n\)と\(B\)に対してループを回すことによって様々な\(n\)と\(B\)の組み合わせに対してSuccessive Halvingを実行することができるようなアルゴリズムになっています．

おわりに

今回は，機械学習のハイパーパラメータ最適化手法であるSuccessive Halvingについて紹介し，その性能を理論的に解析しました．やはり理論的保証があると嬉しいので，自分で提案したアルゴリズムに対しても理論的保証を与えていきたいですね！

非常に長いブログとなりましたが，最後まで読んでくださりありがとうございました．

参考文献

• Bergstra, James S and Bardenet, Rémi and Bengio, Yoshua and Kégl, Balázs : Algorithms for hyper-parameter optimization, Advances in neural information processing systems (2011)
• Hutter, Frank and Hoos, Holger H and Leyton-Brown, Kevin : Sequential model-based optimization for general algorithm configuration, International Conference on Learning and Intelligent Optimization (2011)
• Jamieson, Kevin and Talwalkar, Ameet : Non-stochastic best arm identification and hyperparameter optimization, Artificial Intelligence and Statistics (2015)
• Li, Lisha and Jamieson, Kevin and DeSalvo, Giulia and Rostamizadeh, Afshin and Talwalkar, Ameet : Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization, The Journal of Machine Learning Research (2018)