Abstract
ベイズ最適化（BO）は伝統的に、関数評価が高価であるため観測が少ないブラックボックス問題を解いてきました。しかし近年では、関数評価がより安価で観測が豊富な問題にBOを適用することへの関心が高まっています。この状況では、多数の観測 N へのスケーリングがガウス過程（GP）サロゲートによって妨げられます。具体的には、GPのハイパーパラメータ推定は
\mathcal{O}(N^3) でスケールし（近年の実装では概ね
\mathcal{O}(N^2) へと低減されています）、さらにそれがBOの各反復ごとに繰り返されます。多くの手法は獲得（acquisition）時点でのスケーリングを改善しますが、ハイパーパラメータ推定のスケールは依然として不十分であり、それがボトルネックになります。私たちは、GPの軽量な代替としてエピステミック最近傍（Epistemic Nearest Neighbors, ENN）を提案します。ENNは、K近傍の観測から関数値と不確実性（エピステミックおよびアレアトリック）を推定します。ENNは、推定と獲得の両方で
\mathcal{O}(N) でスケールします。私たちのBO手法であるTuRBO-ENNは、TuRBOにおけるGPサロゲートをENNに置き換え、さらにThompsonサンプリングによる獲得関数を
\mathrm{UCB} = \mu(x) + \sigma(x) に置き換えます。ノイズのない問題という特別な場合には、
\mathrm{UCB} を
\mu(x) と
\sigma(x) に対する非支配ソートで置き換えることで、推定をまったく省略できます。経験的に、TuRBO-ENNは、最大50,000の観測において、TuRBOと比べて提案時間（すなわち推定時間＋獲得時間）を1〜2桁のオーダーで削減することを示します。
