Deterministic Zeroth-Order Mirror Descent via Vector Fields with A Posteriori Certification

技術要約：ベクトル場を用いた、事後検証可能な決定論的ゼロ次ミラー降下法

1. 問題設定
本論文は、中次元における決定論的なゼロ次（勾配を用いない）最適化の課題に取り組んでいる。具体的には、勾配の計算が不可能、極めて高コスト、あるいは数値的に不安定な目的関数（例：対数行列式を含む行列関数や量子相対エントロピーなど）を対象としている。標準的なミラー降下法（MD）は、ブレグマンダイバージェンスを通じて幾何学に適合した最適化を提供するが、伝統的には正確な勾配に依存している。既存の決定論的微分なし最適化（DFO）手法（直接探索法や信頼領域モデルなど）は、通常、ユークリッド幾何学に基づき、停留性指標に焦点を当てているが、最終イテレートの関数値保証には至っていない。対照的に、ランダム化されたゼロ次手法は期待値ベースの境界を提供するものの、再現性や実行ごとの検証可能性（run-wise certification）を欠いている。本研究の核心的な問題は、ブレグマン幾何学を維持し、関数値のみを利用し、かつ明示的で検証可能な最終イテレートの収束保証を提供する、決定論的なゼロ次フレームワークを開発することである。

2. 手法
著者らは、一般化された$\Omega$駆動型ミラー降下法のフレームワークを提案している。このアルゴリズムは、勾配 $\nabla f(x)$ の代わりに、関数値から決定論的に構築された一般化ベクトル場 $\Omega(x)$ を用いる。

• 一般化更新則: 更新は、現在の値 $x_j$ を双対空間へ写像する $\theta_j = \nabla \Phi(x_j)$、ステップ $\theta_{j+1} = \theta_j - \eta_j \Omega(x_j)$ の実行、そして元の空間への写像 $x_{j+1} = (\nabla \Phi)^{-1}(\theta_{j+1})$ からなる。
• 事後検証（A Posteriori Certification）: 解析は、軌跡ごとの相対平滑性条件（式2.5）：$\eta_j D_{f,\Omega}(x_{j+1} \| x_j) \leq D_\Phi(x_{j+1} \| x_j)$ に基づいている。これはグローバルな仮定とは異なり、実現されたイテレートに沿ってチェックされる。これが満たされる場合、明示的な最終イテレートの保証が得られる。
• 穿孔近傍の一般化スター凸性（Punctured-Neighborhood Generalized Star-Convexity）: ゼロ次オラクルに固有の近似誤差を扱うため、緩和されたスター凸性条件を導入している。これは、$\langle \Omega(x), x - x^* \rangle \geq f(x) - f(x^*)$ という条件が、最適解 $x^*$ の周囲の小さな近傍 $U$ の外側でのみ成立することを要求する。これにより、ゼロ次オラクルの解像度によって決定される明示的な「エラーフロア」を分離している。
• 決定論的なインスタンス化: 本フレームワークは、中次元において決定論的な中心差分法を用いてインスタンス化される。ベクトル場 $\Omega(x)$ は、$2d$ 個のオフセンターの関数評価（および再利用可能な1つの中心値）を用いて構築される。
• ロバストな円錐優位性（Robust Conic Dominance）: 技術的な主要貢献として、有限差分ベクトル場が特定の集合 $V_{\epsilon, c}$ の外側で、要求されるスター凸性条件を満たすことを証明している。これは、問題をロバストな円錐優位性の設計問題として定式化することで達成され、単一のスケーリングされたプロキシ方向が、不確実性の円錐内にあるすべての許容可能な真の方向を支配することを保証している。

3. 主な貢献

• 統一フレームワーク: 本論文は、様々な情報幾何学的アルゴリズム（一般化されたブラハット・アリバト更新を含む）や決定論的な有限差分スキームを包含する、$\Omega$駆動型ミラー降下法の一般的なテンプレートを確立している。
• 軌跡ごとの検証可能性: 実行ごとの、検証可能な証明書を提供するメカニなるを提供している。もし軌跡に沿って相対平滑性の不等式が保持されるならば、アルゴリズムは、グローバルな平滑性仮定に依存しない、特定の最終イテレートの関数値境界を保証する。
• 明示的なエラーフロア解析: 決定論的な有限差分を用いる際、著者らは「レート＋フロア」型の収束境界を導出している。誤差は、問題の条件数と有限差分ステップサイズ $\epsilon$ によって決定される近傍の外側で、$O(1/t)$ で減少する。また、エラーフロアは明示的に特徴付けられている。
• 幾何学的結合: 本研究は、ブレグマン・テレスコーピング恒等式、決定論的検証、および決定論的ゼロ次最適化の文脈におけるロバストな円錐幾何学（特に二次の円錐双対性）を結びつける、隠れた幾何学的構造を明らかにしている。

4. 主な結果

• 定理 2.1 & 2.3: 軌跡ごとの相対平滑性条件および穿孔近傍の一般化スター凸性の下で、アルゴリズムは以下を保証する：
  $$f(x_t) - f(x^*) \leq \max \left( \frac{D_\Phi(x^* \| x_1)}{\sum_{j=1}^{t-1} \eta_j}, \max_{x \in U} (f(x) - f(x^*)) \right)$$
  この境界は、収束率（ブレグマンダイバージェンスとステップサイズによって駆動）と、近似誤差（近傍 $U$ によって駆動）を分離している。
• 定理 6.4 & 系 6.6: 決定論的な中心差分を用いてインスタンス化した場合、例外集合 $V_{\epsilon, c}$ は、半径 $\epsilon\sqrt{d}$ に比例するユークリッド球内に含まれることが示される。これにより、エラーフロアがこの $\epsilon$ 近傍内の目的関数の変動によって決定されるという具体的な境界が得られる。
• 実現可能性（定理 5.1）: ステップサイズが十分に小さい場合、軌跡ごとの相対平滑性条件は常に実現可能であることを証明しており、これにより、証明書駆動型ラインサーチの使用を正当化している。

5. 意義と主張
本論文は、決定論的なゼロ次最適化と幾何学に配慮したミラー降下法との間の溝を埋めるものである。その主な意義は以下の通りである：

1. 決定論と検証可能性: 再現性と監査可能性（例：科学計算、安全性が重視される設計）を必要とするアプリケーションに適したフレームワークを提供すること。ここでは確率的手法は不十分である。
2. 幾何学的柔軟性: 勾配が利用できない状況においても、Bregman幾何学（単体、エントロピー、または正定値制約を持つ問題に不可欠）の利点を拡張すること。
3. 理論的洞察: ゼロ次ミラー降下法において、最終イテレートの保証のために重要な構造的仮定は、古典的な凸性そのものではなく、穿孔近傍の一般化スター凸性条件であることを示している。この条件は、有限差分近似の解像度の限界を自然に受け入れるものである。
4. 方法論的転換: グローバルな仮定から、事後的、軌跡ごとの証明書へと焦点を移すことで、実務者が最悪ケースの理論的境界ではなく、実際の実行データに基づいて収束保証を検証できるようにしている。

著者らは、本研究を既存のDFOの伝統に対する補完的なものとして位置づけており、Bregman幾何学が保持される特定のインターフェースを提供し、関数値のみのオラクルを用いた最終イテレートの関数値に対する、初の軌跡ごとの検証可能なミラー降下型の証明書を提供している。