The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression

技術要約：線形回帰におけるマイオピック（近視眼的）なベイズ能動学習のリスクに対する近似比

問題設定
本研究は、予算制約下におけるベイズ線形回帰における最適なデータ選択という根本的な問いに取り組むものである。具体的には、候補となる入力ベクトル $n$ 個の集合 $V = \{v_i\}_{i=1}^n \subset \mathbb{R}^d$ と事前精度行列 $\Lambda$ が与えられたとき、パラメータ推定リスクを最小化するようなサイズ $k$ の部分集合 $S$ を選択することを目的とする。リスクは、事後共分散行列のトレースとして以下のように定義される：
$$f(S) := \text{tr}\left( \left( \Lambda + \sum_{i \in S} v_i v_i^\top \right)^{-1} \right)$$
能動学習の文脈において、これは「マイオピック（近視眼的）」な設定に対応しており、アルゴリズムは長期的な計画の代わりに、即時的なリスク減少を最小化する一点の最適選択を繰り返す。この集合関数を厳密に最適化することはNP困難であるが、貪欲法（グリーディ・アルゴリズム）が標準的なヒューリスティックとして用いられる。これは、リスクの減少量を最大化する点を逐次的に追加していく手法である。

手法および理論的枠組み
本論文は、リスクの「減少量」に着目する従来の解析手法（これまでの研究対象）から、リスク関数の「逆数」である $F_{\text{reciprocal}}(S) = 1/f(S)$ へと分析の焦点を移すことで、貪欲法の性能を分析している。

1. 近似劣モジュラ性： 著者らは、$F_{\text{reciprocal}}$ が近似的に劣モジュラであることを示している。これには、Das and Kempe [2018] によって導入された「劣モジュラ性比率（submodularity ratio）」$\gamma$ の概念を用いている。リスク減少関数の劣モジュラ性を境界とする従来の手法は、最終的なリスクに対して空虚な（意味のない）境界を与える可能性があるが、本研究では、逆数リスクの劣モジュラ性比率の下限を導出している。
2. 主要パラメータ（MILS）： 本研究の重要な貢献は、最大初期レバレッジスコア（Maximum Initial Leverage Score: MILS） と定義される、問題依存のパラメータを特定したことである：
   $$h_{\max} = \max_{i \in [n]} v_i^\top \Lambda^{-1} v_i$$
   著者らは、逆数リスクの劣モジュラ性比率が $(1 + h_{\max})^{-1}$ によって抑えられることを証明している。
3. 近似保証： 導出された劣モジュラ性比率と、近似的に劣モジュラな関数の貪欲最大化に関する既存の理論結果を組み合わせることで、貪欲法によるリスクの近似比の上限を導出している。

主な貢献および結果

• リスク自体に対する初の定数倍保証： 本論文は、A-最適およびV-最適実験計画における、貪欲法によって達成される「リスクそのもの」に対する初の定数倍近似保証を提供している。近似比は以下のように証明されている：
  $$\frac{f(S_{\text{greedy}})}{f(S^*)} \leq h_{\max} + \frac{1}{1 - 1/e} \approx h_{\max} + 1.582$$
  この結果は、貪欲法の性能が最大初期レバレッジスコアに対して線形にスケールすることを示している。

• 境界のタイト性（厳密性）： 著者らは、ハダマール行列を用いた明示的な問題インスタンスの族を構築することで、導出された境界が絶対定数までタイトであることを示している。具体的には、貪欲法のリスクが最適リスクに対しておよそ $h_{\max}$ 倍大きくなるインスタンスが存在することを示した。これにより、 $h_{\max}$ への依存性は分析上の産物ではなく、必要不可欠なものであることが確認された。

• 従来境界の限界： 数値シミュレーションを通じて、本論文は、リスク減少に基づく既存の近似保証（例：Bian et al. [2017], Chamon and Ribeiro [2017]）が、特に初期リスク $f(\emptyset)$ が大きい場合、予算が小さい段階で空虚な（最適リスクの下限を与えない）ものになり得ることを示している。対照的に、新しい境界は依然として情報量を持つ。

意義および主張
本論文は、マイオピックな能動学習に関する文献における重要なギャップを埋めるものである。貪欲法がリスクの「最適減少量」に対して定数分の割合を達成することはよく知られているが、最終的な「リスク自体」に対して定数倍の近似を実現するかどうかは、これまで不明であった。

著者らは、実用的なベイズ線形回帰のほとんどの能動学習アルゴリズムが、多段階の計画の困難さを避けるために、マイオピック（一歩先）の計画に依存しているため、この結果は基本的であると主張している。本研究は、最大初期レバレッジスコアが小さい場合に、このようなマイオピックな戦略が、完全に計画された戦略とほぼ同等の性能を発揮するという理論的な裏付けを初めて提供した。著者らは、本研究を、適応的な選択がオフラインでの選択と等価ではない他のモデルの分析に向けた基礎となるものと位置づけている。