技術要約：Blackwellの接近可能性と勾配平衡は同等である

1. 問題設定と背景

本論文は、オンライン学習の広範な展望における、最近導入されたオンライン最適化フレームワークである勾配平衡（Gradient Equilibrium: GEQ）（Angelopoulos et al., 2025）の理論的な位置付けを扱う。GEQは、オフライン最適化における一次停留性の概念をオンライン設定へと一般化したものである。具体的には、決定列 $\{\theta_t\}$ がGEQを達成するとは、損失関数の劣勾配の時平均がゼロに収束することを指す：
$$\left\| \frac{1}{T} \sum_{t=1}^T g_t(\theta_t) \right\|_2 \to 0 \quad (T \to \infty \text{ のとき}).$$

GEQは、後悔最小化（Regret Minimization: RM）やBlackwellの接近可能性（Blackwell Approachability: BA）といった確立されたフレームワークと構造的な類似性を共有しているが、先行研究では、GEQのエラーと後悔は比較不能な目的関数であることが示されている。ある決定列は、後悔が消失することなくGEQを達成し得、またその逆も然りである。さらに、GEQが達成される条件（例：ベクトル場の復元性/restorativity）は、後悔最小化に必要な条件（例：凸性）とは異なる。したがって、GEQと、より広範なオンライン学習のエコシステムとの間の正確なアルゴリズム的関係は不明なままであった。

本論文が調査する中心的な問いは、GEQが意味論的な違いにもかかわらず、Blackwellの接近可能性、ひいては後悔最小化やキャリブレーションと同等のアルゴリズム的性質を持つかどうかである。

2. 手法

著者らは、GEQとBlackwellの接近可能性の間で、**ブラックボックス・オラクル簡約（black-box oracle reductions）**を確立している。これらの簡約は、一方の問題に対するアルゴリズムを、漸近的なエラー率の損失なしに他方の問題に対するアルゴリズムへと変換できることを示している。

2.1 GEQからBlackwellの接近可能性への簡約

著者らは、GEQ問題をBlackwellの接近可能性問題の特定のインスタンスとして解釈している：

• 行動集合： 学習者の行動集合は決定空間 $\Theta = \mathbb{R}^d$ であり、自然（Nature）の行動集合はベクトル場のクラス $\mathcal{G}$ である。
• 利得関数： 利得は $f(\theta, g) = -g(\theta)$ と定義される。
• ターゲット集合： ターゲット集合は単集合の原点 $\{0\}$ である。

このマッピングの下では、GEQを達成することは、利得の時平均を原点へと導くことと同等である。著者らは、**復元性（restorativity）**条件（GEQの十分条件）が、Blackwellの条件（接近可能性の必要十分条件）を包含することを証明している。

• 課題： この簡約のために有効な半空間オラクル（halfspace oracle）を構築するには、学習者が利用できない復元性のホライゾン $h$ に関する知識が必要となる。
• 解決策： 著者らは、接近方向を増大関数 $\alpha(t)$ によってスケーリングする近似半空間オラクルを提案している。これにより、復元性条件が（具体的には $\lceil \alpha^{-1}(h) \rceil$ 回を除いて）すべてのラウンドで保持されることが保証される。ロバストなBAオラクル（限定的な数のエラーを許容するもの）を利用することで、この簡約は基礎となるBAアルゴリズムの漸近的なエラー率を維持する。

2.2 Blackwellの接近可能性からGEQへの簡約

逆の簡約は、BAアルゴリズムをGEQアルゴリズムへと変換する。

• 円錐（Conic）の場合： まず、ターゲット集合 $S$ が円錐である場合を考える。著者らは、決定集合が極円錐 $S^\circ$ であり、ベクトル場がBAの利得関数と半空間オラクルから導出されるGEQ問題を構築する。GEQオラクルは接近方向を提供し、それは半空間オラクルを介して行動へとマッピングされる。
• 一般ケース（制約なしへの変換）： 主要な技術的貢献は、制約付き決定集合 ($\Theta \subseteq \mathbb{R}^d$) を持つGEQから、制約なしの集合 ($\Theta = \mathbb{R}^d$) を持つGEQへの簡約である。著者らは、スケーリングされた射影残差項を含む修正されたベクトル場を導入している。この項は、新しいベクトル場が復元的であることを保証し、かつ修正された場における制約なしのGEQを達成することが、元の場における制約付きのGEQを達成することを保証する。
• 一般のターゲット集合： 非円錐のターゲット集合に対しては、「円錐リフティング（conic lifting）」の議論（Abernethy et al., 2011に従う）を用いて、BA問題を高次元の円錐接近可能性問題へと変換し、それを制約なしのGEQオラクルによって解く。

3. 主な貢献と結果

3.1 アルゴリズム的同等性

主要な結果は、GEQとBlackwellの接近可能性の間のアルゴリズム的同等性の確立である。

• 定理 3： 復元性を満たす任意のGEQ問題は、エラー率 $O(\text{BAErr}(T)/T)$ でロバストなBAオラクルを用いて解くことができる。
• 定理 9： 任意のBA問題（円錐ターゲット集合を持つ場合）は、エラー率 $O(\text{GEQErr}(T)/T)$ で制約なしのGEQオラクルを用いて解くことができる。
• 系： BA、RM、およびキャリブレーション間の既知の簡約と組み合わせることで、これはGEQが後悔最小化およびキャリブレーションとアルゴリズム的に同等であることを意味する。

3.2 必要十分条件

本論文は、GEQが達成可能であるための必要十分条件としてBlackwellの条件を特定している。以前は、十分条件としての復元性のみが知られていた。著者らは、復元性が（Projected OGDのような）扱いやすいアルゴリズムを設計するための実用的な条件である一方で、Blackwellの条件が解明可能性の正確な特性化を提供するものであることを明確にしている。

3.3 精緻化された保証の転移

これらの簡約により、洗練された性能保証を一つのフレームワークから別のフレームワークへと転移させることが可能になる：

• 楽観性（Optimism）： 予測可能な損失系列を活用する楽観的な後悔最小化アルゴリズムをGEQの簡約に組み込むことで、著者らは、最悪ケースのノルムではなく予測誤差に応じてスケールする楽観的エラー境界を持つGEQアルゴリズムを導出している。
• 強適応性（Strong Adaptivity）： 同様に、任意のサブインターバルで良好に動作する強適応的な後悔アルゴリズムは、強適応的エラー境界を持つGEQアルゴリズムへと変換できる。
• パラメータフリーの後悔最小化： 逆に、単純なGEQアルゴリズム（定数ステップサイズ $\eta=1$ のオンライン勾配降下法など）をBAの簡約に組み込むことで、著者らは、ステップサイズのチューニングを必要とせず、損失ベクトルのノルムの上限 $L$ や時間ホライゾン $T$ の事前知識を必要としない後悔最小化アルゴリズムを導出している。

4. 意義と主張

本論文は、GEQが意味論的に異なる保証（相対的な競合相手に対するパフォーマンスではなく、勾配の絶対的な収束）を提供するものの、アルゴリズムの能力という点では、古典的なフレームワークと同等の強力さを持つと主張している。

• 統一： 本研究は、GEQ、BA、RM、およびキャリブレーションが、同じ基礎的なアルゴリズム構造の異なる側面であることを示し、オンライン学習のフレームワークに関する理解を統一する。
• 実用的な影響： これらの簡約は、新しいアルゴリズムの「設計パス」を提供する。研究者は、既存の高度に最適化されたアルゴリズム（例：後悔最小化に関する膨大な文献）を利用して、別の領域（例：オンライン共形予測や勾配平衡）の課題を、車輪の再発明なしに解決することができる。
• 堅牢性： 適切なリフティングや射影技術が使用される限り、決定集合が制約されている場合やターゲット集合が非円錐である場合でも、結果は保持される。

著者らは、これらの簡約が効率的かつブラックボックス的であることを明示している。これは、基礎となるオラクルの内部的な変更を必要とせず、それらをクエリする能力のみを必要とすることを意味する。このモジュール性は、これらの理論的洞察を実用的なアルゴリズム設計へ即座に適用することを容易にする。