技術要約：ゼロ次ヘッセ行列近似の再考：単一ステップ・ポリシー最適化の観点から

1. 問題設定

ゼロ次（ZO）最適化は、目的関数 $F(\theta) = \mathbb{E}_\xi[f(\theta; \xi)]$ が、ノイズを含む関数評価を通じてのみアクセス可能なブラックボックスであるシナリオに対処するものである。ZO勾配推定は確立されているが、正確なZOヘッセ行列近似は、特に高次元かつノイズの多い設定において、依然として大きな課題となっている。

正確な曲率情報は、以下において極めて重要である：

• 微分フリーのバイレベル最適化（Bilevel Optimization）。
• 不確実性の定量化（Uncertainty Quantification）。
• 大規模言語モデル（LLM）の曲率を考慮したファインチューニング。

既存の手法は、主に2つの制限に直面している：

1. 高分散： 古典的なランダム化エスティメータ（例：Stein型エスティメータ）は、高次元の設定においてしばしば高分散となり、最適化を不安定にする。
2. 限定的な範囲： 先行研究は主にヘッセ行列 $\nabla^2 F(\theta)$ 自体の推定に焦点を当ててきた。二次のZO更新に不可欠な正則化された逆ヘッセ行列 $(\nabla^2 F(\theta) + \lambda I_d)^{-1}$ および逆ヘッセ行列と勾配の積 $(\nabla^2 F(\theta) + \lambda I_d)^{-1}\nabla F(\theta)$ への注意は限定的である。
3. クエリ効率： 素朴な有限差分法は $O(d^2)$ のクエリを必要とする一方、既存のランダム化手法は、分散低減とクエリ再利用のバランスを効果的に取ることができないことが多い。

2. 手法

2.1. 理論的枠組み：ポリシー最適化の観点

著者らは、ZOヘッセ行列近似を**単一ステップ・ポリシー最適化（PO）**の観点から再解釈する統一的なフレームワークを提案している。

• 平滑化された目的関数： ZO目的関数は、平滑化された目的関数 $F_\mu(\theta) = \mathbb{E}_{x \sim \pi_\theta(x)}[\mathbb{E}_\xi[f(x; \xi)]]$ として再定式化される。ここで $\pi_\theta$ はパラメータ化されたサンプリング・ポリシー（例：ガウス分布 $N(\theta, \mu^2 I_d)$）である。
• ヘッセ行列の恒等式： ポリシー勾配を微分することにより、著者らは平滑化された目的関数の一般的なヘッセ行列恒等式を導出している：
  $$\nabla^2 F_\mu(\theta) = \mathbb{E}_{x \sim \pi_\theta(x)} \left[ H_{\pi_\theta} \cdot \mathbb{E}_\xi[f(x; \xi)] \right]$$
  ここで $H_{\pi_\theta}$ はポリシーの対数密度（log-density）のヘッセ行列である。
• エスティメータの統一： この視点は、古典的なStein型エスティメータ（One-point, Two-point, Three-point）が、ベースライン（例：ゼロ・ベースライン、アンカー・ベースライン $f(\theta)$、またはアンチセティック・サンプリング）の選択のみによって区別される、このフレームワークの特殊なケースであることを明らかにしている。

2.2. ZoVH: 分散低減ヘッセ行列エスティメータ

POフレームワークに基づき、著者らはZoVH（Zeroth-Order Variance-reduced Hessian）を導入する。これは2つの主要な技術を用いている：

1. 最適な平均ベースライン：

   • 勾配エスティメータではベースラインがヒューリスティックであることが多いが、著者らは、ランク1の恒等式から導出されるヘッセ行列エスティメータに対して、平均ベースライン $\hat{b} = \frac{1}{K}\sum f(x_k)$ が不偏性を維持する唯一の選択であることを証明している。
   • 理論的に、このベースラインはすべての定数ベースラインの中でエスティメータの分散を最小化することが証明されている。

2. クエリ再利用戦略：

   • クエリコストを増大させることなく分散をさらに低減するために、ZoVHは過去の関数クエリの履歴バッファを利用する。
   • これはPOフレームワーク内におけるオフポリシー学習として解釈され、過去のイテレートから生成された履歴データが、現在のヘッセ行列を推定するために重要度サンプリング（importance sampling）を介して再重み付けされる。
   • これにより、追加の関数評価を行うことなく、サンプルサイズを $K$ から $NK$（$N$ は履歴の長さ）へと実質的に増加させることができる。

2.3. 効率的な逆行列近似

実用的な二次の更新を可能にするため、論文ではZoVHを逆ヘッセ行列および逆ヘッセ行列・勾配積の近似へと拡張している：

• 逆ヘッセ行列： 正則化されたランク $K$ のヘッセ行列エスティメータの逆行列を効率的に計算するために、**ウッドベリーの行列恒等式（Woodbury matrix identity）**を利用する。これにより、高密度の $d \times d$ 行列を反転させることなく、$O(K^2 d)$ または対角近似を用いた $O(Kd)$ で計算が可能となる。
• バイアス補正された積： 勾配とヘッセ行列の推定に同じ乱数方向を使用する場合、相関バイアスが生じる。著者らは、このバイアスを補正するためのleave-one-out戦略を提案しており、これにより最小限のオーバーヘッドで $(\nabla^2 F + \lambda I)^{-1}\nabla F$ を効率的に計算できる。

3. 主な貢献

1. 統一されたPOの視点： 一般的なZOヘッセ行列エスティメータと、平滑化されたPO目的関数のヘッセ行列との間の理論的な等価性を確立し、古典的なランダム化エスティメータをベースライン選択の特定事例として統一した。
2. ZoVHアルゴリズム： 完全なヘッセ行列、その正則化された逆行列、およびバイアス補正された逆ヘッセ行列・勾配積のための、包括的な分散低減エスティメータ・スイートを開発した。
3. 理論的保証：
   • 平均ベースラインを用いたヘッセ行列エスティメータの不偏性を証明した。
   • 平均ベースラインの分散最適性を示した。
   • ZoVHスイート全体に対する誤差境界（バイアス・分散分解）を提供した。
   • 結果として得られる曲率を考慮したZOアルゴリズムが、$\epsilon$-停留点に収束するという収束保証を確立した。
4. 実用的な効率性： クエリ予算を膨らませることなくサンプル効率を高めるクエリ再利用メカニズムを導入し、高次元の問題（LLMのファインチューニングなど）に適した安定した逆行列近似を導出した。

4. 実験結果

著者らは、合成ベンチマーク、ニューラルネットワークの学習、およびブラックボックス敵対的攻撃を用いてZoVHを検証した。

• ヘッセ行列推定の精度：

  • 合成関数（Quadratic, Rosenbrock, Styblinski-Tang）およびCNNレイヤーにおいて、ZoVH（クエリ再利用 $N=4$ 付き）は、古典的なSteinおよびCentral-Differenceエスティメータと比較して、一貫して最も低いフロベニウスノルム誤差を達成した。
  • ZoVH ($N=1$) は、QuadraticおよびRosenbrock関数において、Central-Differenceエスティメータに対して8倍の精度向上を示した。
  • CNNレイヤーにおいて、ZoVH ($N=4$) はCentral-Differenceエスティメータと比較して9倍の誤差低減を達成した。

• 最適化の収束：

  • 合成最適化タスクにおいて、ZoVH ($N=4$) は、収束速度と最終精度の両面でVanilla ZOO、HiZOO、およびZoARを大幅に上回り、Vanilla ZOOに対して平均22倍の高速化を達成した。
  • ブラックボックス敵対的攻撃において、ZoVH ($N=4$) は、Vanilla ZOOと比較して、攻撃を成功させるために必要なイテレーション数を4分の1に削減した。

• LLMのファインチューニング：

  • GLUE/SuperGLUEタスクにおけるOPT-1.3BおよびOPT-13Bモデルのファインチューニングに適用。
  • ZoVHは、MeZOやHiZOOと比較して、より速い収束と高いテスト精度を示した。
  • 実行時間とメモリのオーバーヘッドは最小限であり、ZoVHはMeZOよりわずかに遅い程度で、保持するメモリも（スカラー値とシードのみであるため）無視できるほど少なかった。

5. 重要性と主張

本論文は、ZoVHが曲率を考慮した微分フリー最適化の堅牢な基礎を提供すると主張している。ZO近似とポリシー最適化の間の溝を埋めることで、本研究は以下を実現している：

• 理論的な明晰さ： 特定のエスティメータがなぜ機能するのか、そしてベースライン選択を通じてどのように最適化できるのかを説明する厳密な導出。
• 実用的な有用性： 高価な完全有限差分スキームのクエリコストを課すことなく、実世界のアプリケーション（LLMを含む）において優れた推定精度と収束性能を実現する手法。
• スケーラビリティ： 効率的な逆行列近似とクエリ再利用を通じて、高次元の問題（LLMにおける数百万のパラメータなど）を扱う能力を提供し、従来は実用的ではなかったブラックボックス設定における二次最適化を可能にする。

著者らは、手法が平滑化バイアス（ZO手法に固有のもの）を導入するものの、分散低減とクエリ効率の利点がこのトレードオフを大きく上回り、ノイズの多い高次元環境においてより速く安定した収束をもたらすと強調している。