Online Convex Optimization with Sublinear Noisy Probes

技術要約：劣線形ノイズ付きプローブを用いたオンライン凸最適化

問題設定
本論文は、凸集合 $K \subseteq \mathbb{R}^d$ 上におけるオンライン凸最適化（OCO）を調査している。標準的な設定では、学習者は各ラウンド $t$ において決定 $x_t \in K$ を選択し、敵対的に選ばれた凸損失 $f_t(x_t)$ を被り、フルフィードバック（関数 $f_t$ またはその劣勾配）を受け取る。目的は、事後的に最適な固定決定に対するリグレットを最小化することである。

著者らは、2つの最近の研究（エキスパート設定における劣線形ベストエキスパート・クエリ [Russo et al., 2024] と、OCOにおけるペア比較フィードバック [Bhaskara et al., 2023b]）を一般化する統一的なプロービング・モデルを導入している。このフレームワークにおいて、学習者は予算 $k \le T$ のペアワイズ・プローブを与えられる。プロービングが行われるラウンドでは、$x_t$ を選択する前に、学習者は2つの点 $\{y_{t,1}, y_{t,2}\} \subseteq K$ をクエリし、どちらの点がより小さい損失を持つかという指示を受け取ることができる。極めて重要な点は、これらのプローブにはノイズが含まれることである。確率 $\delta$ で、オラクルは「高い」方の損失を持つ点を返し（「誤った」回答）、確率 $1-\delta$ で正しい最小値を持つ点を返す。ノイズパラメータ $\delta \in [0, 1]$ は学習者には未知である。

プロトコルは、学習者が特定のラウンドでプロービングを行うかどうかを決定する前に、損失関数の列 $\{f_t\}_{t=1}^T$ を事前にコミットする**無差別な敵対者（oblivious adversary）**を想定している。この制約は極めて重要である。もし敵対者がプロービングの決定に適応できる場合（例：プローブが行われるラウンドの損失を0に設定するなど）、プローブは役に立たなくなり、リグレット界が $\Theta(\sqrt{T-k})$ に劣化してしまうためである。

手法
提案されているアルゴリズムは、連続指数重み付け法（CEW）の適応的なプローブ拡張版である。核心となる技術的洞察は、分散減少効果と、CEWアルゴリズムの二次（分散ベース）解析に基づいている。

1. プロービングによる分散減少:
   プロービング・ラウンドでは、アルゴリズムは現在の密度分布 $p_t$ から独立に2つの点をサンプリングする。観測されたより低い方の損失を持つ点（またはプローブによって示唆された点）を選択してプレイすることで、期待損失は $p_t$ の下での損失関数の分散 $v_t = \text{Var}_{x \sim p_t}[f_t(x)]$ に比例する量だけ減少する。具体的には、ノイズのないプローブの場合、期待損失は $v_t$ だけ減少する。

2. ノイズ付きプローブの処理（メタ学習器）:
   $\delta$ は未知であるため、アルゴリズムはプローブの示唆に「従う（follow）」か「反転させる（invert）」かを決定するために、軽量なメタ学習器（具体的には AdaHedge）を採用する。メタ学習器は2つのアクション、$F$（従う）と $I$（反転させる）に基づいて動作する。これは、プロービングが行われたラウンドにおけるこれら2つの仮説的なアクションによって発生した損失に基づいて重みを更新する。これにより、アルゴリズムは、プローブが情報量が多い場合（$\delta$ が $1/2$ から遠い場合）にはそれを信頼し、情報量が少ない場合には無視するように適応的に動作できる。

3. リグレット分解:
   リグレット解析は、総損失を2つのコンポーネントに分解する：

   • 非プロービング・ラウンド: アルゴリズムは標準的な CEW 更新に従う。リグレットは、ベースラインのリグレットを累積分散 $V_T = \sum v_t$ に関連付ける二次解析（de Rooij et al., 2014 に倣う）を用いて抑えられる。
   • プロービング・ラウンド: 損失は、メタ学習器のより優れた方のアクション（$F$ または $I$）の損失と、メタ学習器自体のリグレット項によって抑えられる。解析によれば、「より優れた」アクションは、損失の減少が $|1-2\delta|v_t$ に比例することを示す。

主要な結果
本論文は、劣線形のノイズ付きペアワイズ・プローブの予算を用いることで、フルフィードバックの OCO レジームにおける最悪ケースのリグレットを、証明可能な形で改善できることを確立している。

• 一般的な凸損失: 凸集合 $K$ 上の $[0, 1]$ に限定された一般的な凸損失の場合、期待リグレットは以下の通りである：
  $$\text{Reg}_T \le O\left( \min\left\{ \sqrt{dT \ln T}, \frac{dT \ln T}{k |1 - 2\delta|} \right\} \right)$$
  この界は、$T$、$k$、およびノイズパラメータ $\delta$ に関して、（対数因子を除いて）タイトである。リグレットは $\delta \to 1/2$ （コイン投げ）に向かうにつれて滑らかに劣化する。

• エキスパートによる予測: エキスパート設定（単体 $\Delta^{d-1}$ の頂点上の線形損失）という特殊なケースでは、界は以下のように改善される：
  $$\text{Reg}_T \le O\left( \min\left\{ \sqrt{T \ln d}, \frac{T \ln d}{k |1 - 2\delta|} \right\} \right)$$
  これらのレートは、次元 $d$ を含むすべてのパラメータにおいて完全にタイトである。

意義と貢献
著者らは、いくつかの重要な貢献を主張している：

1. 統一: 本研究は、離散的な「ベストエキスパート」プロービング・モデルと、連続的な「ペアワイズ比較」モデルを単一のフレームワークへと統一し、ペアワイズ・プローブが、最適なリグレート・レートを達成するためにベストエキスパート・プローブと同等の情報量を持つことを示している。
2. ノイズへの堅牢性: 特定のノイズモデルやノイズのない状況を想定することが多い先行研究とは異なり、本フレームワークは未知のノイズレベル $\delta$ を扱い、$|1-2\delta|$ に対する最適な依存関係を達成している。
3. 技術的新規性: 解析において、差分プライバシーの仕組みや、勾配ノルムや曲率に関する仮定（Bhaskara et al., 2023b などの先行研究で必要とされていたもの）を回避している。代わりに、分散ベースの減少議論を活用している。
4. 最適性: 論文は（付録Aにおいて）下界も提示しており、エキスパート設定において導出されたレートがタイトであること、および一般的な凸集合において $T, k, \delta$ に関してタイトであることを示している。

著者らは、理論的な保証は強力であるものの、メインのアルゴリズムは凸集合上の積分計算を必要とし、一般には計算困難である可能性があると述べている。同等の保証を達成する効率的なアルゴリズムの開発が、今後の研究課題として挙げられている。