基礎的なベイズ的最適化の概念については説明していません。
記事に誤りがある可能性があります。指摘していただけると幸いです。

はじめに

本記事では、ベイズ最適化のアルゴリズム提案論文に付きがちである、リグレット解析についてお気持ちを説明します。
モチベーションは執筆時点でベイズ最適化のリグレット解析について解説する日本語の記事が無く¹、せっかく勉強したから残しておこうと思った次第です。
数学的な厳密性よりも、気持ちの理解を優先します。
目標は、「リグレット解析の結果の式に入っている$O()$ってなんだ？$\gamma_T$ってなんだ？」という疑問を解消することです。

なお、本記事はGarnett(2023)の書籍に準拠しています。

リグレット解析の目的と手法の流れ

端的には最適化アルゴリズムの最適化の収束性能を統一的に比較するための指標を定め、その指標で比較評価することです。

この指標を定めるために、観測値が最適値にどのくらい近いかを表す最適化誤差が、イテレーションを進めていく過程で漸近的にどのくらい減少するかを定量します。
つまり、用いるデータセットに含まれるデータ数$T$について、$T \rightarrow \infty$の場合を想定します。

ここで、データを何個とった時に最適化が終了した（最適化が収束した）と判定するのか、という問題が生じます。
しかし、観測している現象の目的関数がブラックボックスな問題を扱っていることから「最適化の収束」を定義するのは非常に難しいです²。

一般に、収束について議論を進める上で必要なステップが3つあります。

何らかの最適化誤差の指標を選択すること
考える目的関数の複雑さを決める
選んだ目的関数への最適化誤差に対し評価を行い、$T \rightarrow \infty$での上界を考える

リグレット解析もこの順番で解析を進めます。

本記事のスコープ

3つ目のステップは、それぞれのアルゴリズムによって大きく異なるため、本記事ではアルゴリズム非依存的に考えられる段階までを扱います。
幸いにも1,2つ目のステップには確立された慣習があり、本記事で重点的に扱います。

問題設定

観測により、ガウスノイズ付きの結果が得られる。

y = f(\mathbf{x}) + \varepsilon,\quad \varepsilon \sim \mathcal{N}(0, \sigma^2)

$t$回の観測により得られる観測集合を以下のように表す。

D_t = \{ (\mathbf{x}_i, y_i) \}_{i=1}^t

1. 最適化誤差の指標：リグレット

ベイズ最適化の性能はリグレットで評価され、大きく2つの評価法があります。
ここでリグレットとは、実験者が「あの方策をとっておけばよかった」という後悔の大きさを表しています³。
なお、$\mathbf{x^*}$を最適な条件、$\mathbf{x}_i$を$i$回目の条件、$T$を評価時点でのイテレーション数とします。

単純リグレット

S_T=f(\mathbf{x}^*) - \underset{i\leq T} {\mathrm{max}} \, f(\mathbf{x_i})

累積リグレット

R_T = \sum _{i\leq T} \{f(\mathbf{x}^*) -  f(\mathbf{x_i}) \}

単純リグレットは、最適値とこれまでに観測した出力の最大値の差であり、最適解にのみ興味がある場合に用いられます。
累積リグレットは、各イテレーションについて最適値と出力の差をとって⁴イテレーション$T$まで足し合わせたものであり、途中解にも興味がある場合に用いられます。

以下は意見であるため間違っていたらご指摘いただきたいのですが、私はベイズ最適化の評価手法としては単純リグレットが適切であると考えています。
理由としては、リグレット解析が発展してきたバンディット問題の領域において、最適腕識別問題⁵では単純リグレットを用いており、バンディット問題では累積リグレットとそれに類する指標を用いており、ベイズ最適化は最適腕識別問題に分類されると考えているためです。
実際、ベイズ最適化のアルゴリズム提案論文で累積リグレットを評価指標として使用している例は見たことがなく、単純リグレットが評価指標として用いられています。

これ以降、単純リグレットがベイズ最適化の性能を評価する指標であるという立場で記事を進めさせていただきます。

しかし、単純リグレットには$\max$演算子が入っているように、収束性能を評価するのは難しいです。
そこで、累積リグレットに簡単な変形を施します。
$\frac{R_T}{T} = f(\mathbf{x^*}) - \frac{1}{T}\sum_{i}f(\mathbf{x_i})$とすると、$S_T \leq\frac{R_T}{T} $がわかります。
すると、$\lim _{T\rightarrow \infty} \frac{R_T}{T} = 0$を満たすならば$0 \leq S_T \leq\frac{R_T}{T} \rightarrow 0$となるため、$\lim _{T\rightarrow \infty} S_T = 0$も示すことができます。

以上より最適化アルゴリズムは、単純リグレットの収束よりも強い条件である$\lim _{T\rightarrow \infty} \frac{R_T}{T} = 0$を目指し、この条件のことをNo-regret propertyと言います。

2. 考える目的関数の複雑さを決める

「どれくらいの複雑さの目的関数を用いるか」を決めるには、実用性と一般性のトレードオフを乗り越える必要があります。

実用的に最適化が可能という観点だと、目的関数は滑らか（数学的には曖昧な表現）であるという前提を置くことに相当します。直感的に、滑らかな関数の方が最適化が簡単そうですよね。
一方で目的関数の一般性を保つ観点では、ピーキーな関数含め連続関数空間全体を考えることに相当します。

しかしそれぞれに寄り過ぎると、

実用性を重視し過ぎると本当の目的関数がピーキーな時に現実とは異なる最適解が得られてしまう
一般性を重視し過ぎると最適化の収束が見込めない

という課題があります。

後者の課題について、理論的に収束の証明が不可能であることが直感的にわかる例を示します。

Bという区間以外、全ての区間を観測した場合を考えます。つまり、横軸を条件・縦軸を出力とした左図における目的関数$f$は、区間B以外では観測値をプロットしたものとします。
この目的関数$f$について最適化を行い、左図の黄色星のように最適条件を見つけることができたとします。
しかし、連続関数空間全体を許容する立場であると、中図のように実は区間Bにおける形状が「針」のような関数$g$であることを否定できません。
この場合、区間Bも観測し終えた関数$f+g$において、真の最適値は右図のように赤色星となり、はじめに左図で導いた最適条件は間違いであったということになります⁶。

より一般の場合を考えてみると、連続関数の区間を全て観測することは不可能ですが、連続関数空間全体を許容する立場であると、未観測空間により大きな目的関数値があることを否定できません。つまり、「最適化が収束した」と示すことができません。

以上より、目的関数が連続関数であると想定すると、収束の証明が不可能という課題があります。
そこで解決策として、目的関数に対して「少し滑らか」な仮定をおき「針」を防ぐことを考えます。
この仮定の置き方として以下の2通りがあります。

目的関数をガウス過程から得られるサンプルパスに限定する
目的関数を再生核ヒルベルト空間に限定する

どちらの仮定をおいても同じ結論が得られる⁷ので、今回の記事では前者について気持ちを述べます。
目的関数$f$がガウス過程を満たすという時、使用するカーネルによって$f$の滑らかさを指定可能である、という事実を思い出してみると、この仮定が「少し滑らか」な仮定をおけることも腑に落ちるかなと思います。

3. 選んだ目的関数・最適化誤差に対して評価する

2節において目的関数に対して仮定を置き、「少し滑らか」な複雑さに限定することはできましたが、目的関数がどれくらい最適化する上で難しいかという指標がまだありません。
そこで、まずはその指標を考えます。

そのために用いる直感は、上の図から感じるように

荒い関数は最適化が難しそう
滑らかな関数は最適化が簡単そう

ということです。
さらに、荒い関数を最適化する際には、「針」が存在し得ないくらい密に観測をする必要があり、この目的関数を記述するのに必要な情報が多そう、と感じます。

そこで、関数$f$に対し、情報容量(ある観測回数$T$で取りうる情報量の上界)で定式化することにします。

具体的には、観測集合$D_t$を知ることによる目的関数$f$の情報量の減少量である相互情報量⁸を考え、それの最大値を情報容量$\gamma_T$として定式化します。

I(\mathbf{y}_{1:t}; \mathbf{f}_{1:t}) = H[\mathbf{y}_{1:t}] - H[\mathbf{y}_{1:t} \mid \mathbf{f}_{1:t}] = \tfrac12 \log\bigl\lvert I + \sigma^{-2} K_t\bigr\rvert

\text{情報容量}= \gamma_T = \max_{A:|A| = T} I(\mathbf{y}_A; f_A)

この式に対する解釈を三点述べます。

情報容量を用いる必然性（相互情報量の上界を求める意義）
- 観測点の取り方(アルゴリズム)に依存せず、どんな”ベスト”な選択をしても超えられない、学習量の限界を示すため
$\gamma_T$が小さい、ということは関数$f$はそもそも学習すべき情報が少ない、滑らかな関数であることを表しており、少ない観測数でregretを下げることができそう。
相互情報量は予測分散(共分散行列)を変数とする形に変形でき(第一式最右辺)、(実は)累積リグレットを変形すると予測分散が出てくるため、累積リグレットと情報容量$\gamma_T$を繋げられそう！

導出の詳細

相互情報量 $I(\mathbf{y}_{1:t}; \mathbf{f}_{1:t}) = H[\mathbf{y}_{1:t}] - H[\mathbf{y}_{1:t} \mid \mathbf{f}_{1:t}]$ は、「$f$が未知での不確実性」から、「$f$が既知の時に残る、ノイズ由来の$\mathbf{y}_t$の不確実性」を引いたものであると解釈できます。

まず、条件付きエントロピー$H[\mathbf{y} \mid \mathbf{f}]$を考えます。
$y = f(\mathbf{x}) + \epsilon$より、$\mathbf{y} \mid \mathbf{f} \sim \mathcal{N}(\mathbf{f}, \sigma^2 I)$となります。
ここで多変数ガウス分布のエントロピー公式$H\bigl[\mathcal{N}(0,\Sigma)\bigr] = \frac{1}{2} \log\bigl((2\pi e)^d \lvert \Sigma\rvert\bigr)$を用いて、以下のように書けます。

$$H[\mathbf{y}\mid \mathbf{f}] = \frac{1}{2}\log\bigl((2\pi e)^t\lvert\sigma^2 I\rvert\bigr) = \frac{t}{2}\log\bigl(2\pi e,\sigma^2\bigr)$$

次に、$H[\mathbf{y}]$を考えます。$\mathbf{y} \sim \mathcal{N}(\mathbf{0}, \mathbf{K}_t + \sigma^2 I)$となるため、

\begin{aligned}
H[\mathbf{y}]
&= \frac{1}{2}\log\bigl((2\pi e)^t \,\lvert K_t + \sigma^2 I\rvert\bigr) \\
&= \frac{t}{2}\log(2\pi e) + \frac{1}{2}\log\lvert K_t + \sigma^2 I\rvert
\end{aligned}

となります。

したがって、相互情報量は以下のように表せます。

\begin{aligned}
I(\mathbf{y};\mathbf{f})
&= H[\mathbf{y}] - H[\mathbf{y}\mid \mathbf{f}] \\
&= \Bigl[\frac{t}{2}\log(2\pi e) + \frac{1}{2}\log\lvert K_t + \sigma^2 I\rvert\Bigr]
- \Bigl[\frac{t}{2}\log(2\pi e\,\sigma^2)\Bigr] \\
&= \frac{1}{2}\log\lvert K_t + \sigma^2 I\rvert
- \frac{1}{2}\log\lvert \sigma^2 I\rvert \\
&= \frac{1}{2}\log\lvert \sigma^{-2}(K_t + \sigma^2 I)\rvert \\
&= \frac{1}{2}\log\lvert I + \sigma^{-2}K_t\rvert
\end{aligned}

なお、3行目で$\lvert \sigma^2 I\rvert = \sigma^{2t}$、4行目で行列式の性質$\lvert aA \rvert = a^n\lvert A \rvert$（$A$が$n \times n$行列の場合）を用いています。

ここで、リグレット解析で示したいことに立ち返ると、累積リグレットについて$\lim _{T\rightarrow \infty} \frac{R_T}{T} = 0$を示すこと(no-regret property)でした。
そこで、累積リグレットが予測分散$\sigma_i$を変数としているところを、目的関数の複雑さを表す情報容量$\gamma_T$を変数とする形に変形したいというモチベーションが得られます。

まず相互情報量を、逐次観測ごとの情報増分を足し合わせると解釈すると以下のように書けます。

I(\mathbf{y}_{1:t}; \mathbf{f}_{1:t}) =
\frac12 \sum_{i=1}^t \log\!\Bigl(1 + \frac{\sigma_i^2}{\sigma^2}\Bigr)

この式はまだ$\log$の形になっており、目的は達成されません。
そこで不等式で$\sigma_i$を上から抑えることにより$\log$を登場させ、情報容量$\gamma_T$を使える形に落とし込みます。
天下り的ですが、関数$z^2 / \log (1+z^2)$が$z>0$において単増であることを利用します。
$\sigma_i^2 \le M$なる定数の上界を用意し、$\sigma_i / \sigma$, $\sqrt{M}/\sigma$なる変数を$z$に代入すれば以下になります。

    \frac{\sigma^{-2}\,\sigma^2_i}
    {\log\bigl(1 + \sigma^{-2}\sigma^2_i\bigr)}
    \le
    \frac{\sigma^{-2}M}
    {\log\bigl(1 + \sigma^{-2}M\bigr)}

両辺$\sigma^{-2}$で割り、移行することで以下になります。

\sigma_i^2 \le \frac{M}{\log\bigl(1 + \sigma^{-2} M\bigr)} \log\!\Bigl(1 + \frac{\sigma_i^2}{\sigma^2}\Bigr)

両辺和をとって定数を$c$でまとめると、累積リグレットの上界の式に情報容量$\gamma_T$を用いることができます。

\sum_{i=1}^T \sigma_i^2 \le c \sum_{i=1}^T \frac 12 \log\!\Bigl(1 + \frac{\sigma_i^2}{\sigma^2}\Bigr)
 = c \gamma_T = O(\gamma_T)

まとめ

本記事ではリグレット解析の初歩を扱いました。
1.最適化誤差の指標を定義し、2.目的関数の複雑さを制限・評価指標を作り、3.最適化誤差の式に目的関数の複雑さ$\gamma_T$を組み込む段階まで理解していただけたら幸いです。
数学的な厳密さや、実際に累積リグレットをどう上界できるかの詳細は、ベイズ最適化で初めてリグレット解析を行った論文⁷を参照いただければと思います。
最後まで読んでくださり、ありがとうございました！

2025/07/31に増補改訂版　ベイズ最適化ー適応的実験計画の基礎と実践ーが発売され、リグレット解析の内容が追加されるそうなので、発売以降はそちらをご覧いただいた方が正確かと思います。 ↩
言い換えると、ブラックボックス関数最適化の最中に最適値はわからないため、「最適化誤差」を定義することができません。 ↩
バンディット問題の理論とアルゴリズム (機械学習プロフェッショナルシリーズ) ↩ ↩²
それぞれのイテレーションにおける差分を瞬間リグレット$r_t = f(\mathbf{x}^*) - f(\mathbf{x_i})$と言います。 ↩
今回、最適腕識別問題はバンディット問題に内包されていないとします。³において、「バンディット問題」という用語は累積報酬の最大化のみを指すという立場をとっているため、それに従いました。 ↩
別の言い方をすると、未観測の区間Bにおいて単純リグレットをいくらでも大きくすることができてしまうため、最適化の収束が示せません。また別の言い方をすると、区間Bが未観測の時、最適化方策は目的関数が左図のような形なのか、それとも右図のような形なのか判断することができません。 ↩
Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting ↩ ↩²
相互情報量の対称性を用いて、$I(\mathbf{f}; \mathbf{y}) $の形で解釈しています。 ↩