Generalization of Zeroth-Order Method for Quotients of Quadratic Functions

Jonas Bresch による論文「Quotients of Quadratic Functions に対するゼロ次手法の一般化」の詳細な技術的要約を以下に示す。

1. 問題定義

本論文は、ゼロ次（微分不要）の制約下における一般化された作用素ノルムおよび極値一般化レイリー商の最適化問題を取り扱っている。具体的には、以下の問題を解くことを目的とする：
$$\left\| \frac{A}{B} \right\| := \max_{v \in \mathbb{R}^d \setminus \{0\}} \frac{\|Av\|}{\|Bv\|}$$
ここで、$A \in \mathbb{R}^{m \times d}$ および $B \in \mathbb{R}^{\ell \times d}$ は、前方評価（ブラックボックスアクセス）のみを通じてアクセス可能な行列である。

主要な制約と課題：

• 随伴演算子不要・行列不要： 随伴演算子 $A^T$ および $B^T$ が利用できないか、前方演算子と整合しない（レガシーコード、偏微分方程式ソルバ、トモグラフィーなどで一般的）。
• 適切性： $B$ はフル列ランク（$\text{rank}(B)=d$）である必要があり、これにより $B^TB \succ 0$ となる。
• 既存手法の限界： 最近の最先端のゼロ次手法（例：Bresch ら [7–9]）は、一般化された球面 ($S^{d-1}_{B^TB}$) 上の接空間サンプリングに依存している。これは、探索方向を射影するためにメトリック $B^TB$ またはその平方根の知識を必要とするが、厳密なブラックボックス設定では実行不可能である。

2. 手法

本論文は、制限された接空間ではなく、単位球面全体における無制約サンプリングに基づいた、根本的に異なるアプローチを提案する。

A. 無制約サンプリング戦略

一般化された球面の接空間（$B^TB$ を必要とする）から探索方向 $x_k$ をサンプリングする代わりに、本手法は標準的な単位球面 $S^{d-1}$ から $x_k$ を一様にサンプリングする：
$$x_k = \frac{x}{\|x\|}, \quad x \sim \mathcal{N}(0, I_d)$$
これにより、メトリック依存の射影や随伴情報の必要性が排除される。

B. 閉形式解による最適ステップサイズ

現在の反復点 $v_k$ と探索方向 $x_k$ に対して、アルゴリズムは再traction 経路に沿って目的関数を最大化する最適なステップサイズ $\tau_k$ を求める。経路に沿った目的関数は二次関数の商となる：
$$s_k(\tau) = \frac{\|A(v_k + \tau x_k)\|^2}{\|B(v_k + \tau x_k)\|^2} = \frac{a_k + 2b_k\tau + c_k\tau^2}{d_k + 2e_k\tau + f_k\tau^2}$$
係数 ($a_k, \dots, f_k$) は、$A$ と $B$ の前方評価のみを用いて計算される。

• 理論的ブレイクスルー： 本論文は、最適な $\tau_k$ を求めることが、$2 \times 2$ グラム行列 $M_k$ および $N_k$ を含む2 次元一般化固有値問題を解くことと等価であることを証明している。
• 結果： 特定のランダム方向に対して最適なステップサイズ $\tau_k$ の閉形式解が導出され（定理 3.1）、線探索ヒューリスティクスなしでステップサイズが最適化される。

C. ゼロ次リーマン最適化フレームワーク

本手法は、関数評価のみを用いてリーマン最適化の量に対する推定量を構築する：

1. 勾配推定量： ランダム方向 $x_k$ と最適ステップサイズの論理を用いて、リーマン勾配の不偏推定量を構築する。
2. ヘッシアン推定量（準ニュートン）： 球面上の一様分布の 4 次モーメントを用いて、リーマンヘッシアンの不偏推定量を導出する（系 3.3）。これにより、**ゼロ次準ニュートン法（アルゴリズム 3）**が可能となる。
3. 分散低減： $m$ 個の独立したサンプルを平均化すること（アルゴリズム 2）により、勾配推定量の分散を低減し、収束を加速する。

3. 主要な貢献

1. $S^{d-1}$ 上の無制約サンプリング：
   本論文は、一般化された球面の接空間ではなく、完全な単位球面上で動作するサンプリング方式を導入する。これにより、$B^TB$ またはその随伴の要件が排除され、既存手法が失敗した厳密なブラックボックスシナリオにも手法が適用可能となる。

2. 閉形式の最適ステップサイズ：
   固定またはヒューリスティックなステップサイズを使用する標準的なゼロ次手法とは異なり、本研究は特定の二次関数の商目的関数に対する最適なステップサイズ $\tau_k$ の正確な閉形式解を導出する。これにより、部分問題は解可能な 2 次元一般化固有値問題へと変換される。

3. 不偏ヘッシアン推定：
   著者らは、微分不要の設定におけるリーマンヘッシアンの不偏推定量の原理的な導出を提供する。これにより、明示的な微分なしで曲率情報を捉える**2 次ゼロ次アルゴリズム（準ニュートン法）**の構築が可能となる。

4. 理論的収束保証：

   • 概収束： 反復点の列は、主要な一般化固有空間に概収束する（定理 3.7）。
   • 臨界点解析： 勾配代理変数 ($\alpha_k$) の列が概してゼロに収束することを証明しており、アルゴリズムが最適でない臨界点に留まることを防いでいる（穏やかなスペクトル仮定の下で）。
   • 適切性： ステップサイズ計算における分母が概してゼロにならないことが証明されており、アルゴリズムが適切に定義されていることが保証される。

4. 数値結果

実験は、最大 $d=1000$ の次元を持つ合成ランダムガウス行列を用いて行われた。

• 最先端手法との性能比較：
  • 低次元では、提案手法は最近の接空間サンプリング手法 [9] と同等の性能を示す。
  • 高次元（$d \gg 10$）では、無制約球面サンプリングは接空間手法を著しく上回る。これは、より広い探索空間と、接空間手法で必要となる高価な射影操作（行列 - 行列乗算）の回避に起因する。
• 収束率：
  • 本手法は相対商誤差（RQE）に対して線形収束を示す。
  • 一般化固有方程式に対する最小二乗残差（MSQR）は $O(1/k)$ の収束率を示し、微分不要手法でよく見られる部分線形率よりも優れている。
• 2 次手法の利点：
  準ニュートン変種（アルゴリズム 3）は、1 次変種（アルゴリズム 2）と比較して、臨界点付近でより厳密な収束挙動とより高速な誤差低減を示し、最適点近傍での性能格差を実質的に埋める。

5. 意義

本研究は、スペクトル問題に対する微分不要最適化における重要な進展を表している。

• 実用的影響： 随伴演算子が利用できない、整合しない、または計算コストが高すぎるシナリオ（レガシーシミュレーションコード、複雑な PDE ソルバなど）において、作用素ノルムやレイリー商の計算を可能にする。
• 理論的影響： 多様体上の勾配とヘッシアンの両方に対する不偏推定量を提供することで、ゼロ次ランダム探索とリーマン最適化の間のギャップを埋める。これには明示的な多様体射影は不要である。
• アルゴリズム的効率性： 閉形式のステップサイズと接空間射影なしで動作する能力により、アルゴリズムは計算効率が良く、高次元問題にもスケーラブルである。

要約すると、Bresch は、制約付き接空間サンプリングを無制約球面サンプリングに置き換え、正確なステップサイズを導出し、高次元のブラックボックス設定において既存の最先端手法を上回る厳密な 2 次フレームワークを確立することにより、ゼロ次手法を二次関数の商を扱うように一般化した。