Power Homotopy for Zeroth-Order Non-Convex Optimizations

技術要約：ゼロ次非凸最適化のためのパワー・ホモトピー

問題提起
本論文は、勾配へのアクセスなしに目的関数 $f: \mathbb{R}^d \to \mathbb{R}$ を最大化しなければならない非凸問題における、ゼロ次（ZO）最適化の課題に取り組んでいる。既存の手法であるGS-PowerOptなどは、グローバルな最適解を特定するためにパワー変換されたガウス平滑化を利用しているが、これらは固定された平滑化半径 $\sigma$ に依存している。著者らは、この固定された $\sigma$ 設計における根本的な限界を指摘している。すなわち、グローバルな探索（exploration）と局所的な精緻化（refinement）の間に存在する固有のトレードオフである。大きな $\sigma$ はグローバルな探索を容易にし、サロゲート最適化を加速させるが、サロゲートの極大値の位置を歪めてしまう。逆に、小さな $\sigma$ は局所的な幾何構造を保持するが、イテレートが値の高い領域から遠い場合、勾配信号が弱くなる。

手法：GS-PowerHP
このトレードオフを解決するために、著者らは、パワー変換と原理に基づいた減衰する平滑化半径スケジュールの統合による、シングルループのゼロ次アルゴリズムであるGS-PowerHP（Power-Transformed Gaussian Homotopy）を提案している。

1. 目的関数の変換: この手法は、以下のサロゲート目的関数を対象とする：
   $$F_{N,\sigma}(\mu) := \mathbb{E}_{x \sim \mathcal{N}(\mu, \sigma^2 I_d)}[e^{N f(x)}]$$
   ここで、$N$ はパワーパラメータ、$\sigma$ は平滑化半径である。
2. 減衰スケジュール: 固定された $\sigma$ を使用するGS-PowerOptとは異なり、GS-PowerHPは各イテレーション $t$ において、以下の式に従って平滑化半径を更新する：
   $$\sigma_{t+1} = \sigma_0 \beta^{t+1} + b$$
   ここで、$\beta \in (0, 1)$ は減衰因子であり、$b > 0$ は下限値である。
3. 更新ルール: アルゴリズムは、確率的勾配上昇ステップを実行する：
   $$\mu_{t+1} = \mu_t + \alpha_t \hat{\nabla} F_{N,\sigma_{t+1}}(\mu_t)$$
   勾配推定値は、$\mathcal{N}(\mu_t, \sigma_{t+1}^2 I_d)$ から抽出された $K$ 個のサンプルを用いて計算される。
4. メカニズム: この戦略は、大きな $\sigma$ で開始することで、グローバルな探索中（$\mu_t$ が最適値から遠いとき）に情報量の多い勾配信号を維持し、イテレートが極大値に近づくにつれて $\sigma$ を徐々に減少させ、局所的な精緻化を向上させる。

主な貢献

1. 理論的洞察: 著者らは、GS-PowerOptの固定 $\sigma$ メカニズムに内在する探索と精緻化のトレードオフを特定する形式的な分析を提供している。彼らは、反復計算量が $\sigma^2$ に反比例すること（大きな $\sigma$ が有利）、一方で、サロゲートの極大値と真のグローバル極大値との整合性が $\sigma \to 0$ に伴って改善すること（小さな $\sigma$ が有利）を証明している。
2. アルゴリズムの革新: GS-PowerHPは、パワー変換と増分的な $\sigma$ 減衰メカニズムを明示的に組み合わせた最初のゼロ次手法である。
3. 収束保証: 本論文は、理論的な収束結果（系1および系3）を確立している。緩やかな仮定の下で、GS-PowerHPが期待値においてグローバル極大値の任意の近傍に収束することを証明している。一次停留性への有限時間収束率は $O((d^2 \epsilon^{-1} b^{-2})^{\frac{2}{1-2\gamma}})$ であることが示されており、減衰スケジュールによって、初期の進展を加速させつつ、極限における局所的な精度を確保できることが検証されている。
4. 実証的な優位性: 広範な実験により、GS-PowerHPが、固定 $\sigma$ のベースライン（GS-PowerOptを含む）や他の平滑化ベースのZO手法（ZOSGD、ZO-AdaMM、ZOSLGHなど）を一貫して上回ることが示された。

実験結果
著者らは、以下の項目についてGS-PowerHPを評価した：

• ベンチマーク関数: $d=100$ 次元のAckley関数およびRastrigin関数の最大化。GS-PowerHPは、平滑化ベースの手法の中で最高のフィットネス値を達成し、GS-PowerOptと比較して収束に必要なイテレーション数が少なかった。
• 敵対的攻撃（ブラックボックス）: MNIST、CIFAR-10、およびImageNetの分類器に対する「最も起こりにくい（least-likely）」標的型攻撃に対してテストを行った。
  • ImageNet ($d=150,528$) において、GS-PowerHPは78%の成功率を達成した。これはGS-PowerOpt（47%）やZOSLGHd（67%）を大幅に上回る改善であり、かつ同等の摂動サイズと画像の類似性を維持している。
  • MNISTおよびCIFAR-10においては、競合する平滑化ベースのアルゴリズムよりも小さな摂動ノルムで、100%の成功率を達成した。
• アブレーション研究: 合成目的関数および標的型攻撃を用いた実験により、減衰 $\sigma$ メカニズムが性能向上の主要な要因であり、固定 $\sigma$ バリアントよりも探索と精緻化をより効果的にバランスさせていることが確認された。

意義と主張
本論文は、平滑化半径を静的なハイパーパラメータとしてではなく、適応的な計算リソースとして扱うことで、GS-PowerHPがゼロ次非凸最適化における重要な進歩を遂げたことを主張している。著者らは、このアプローチが、従来のパワー平滑化手法に見られる構造的な緊張（探索と精度の間の葛藤）を解決すると断言している。

本研究の重要性は、極めて高次元な設定（例：ImageNet攻撃）における堅牢なパフォーマンスによって強調されている。そこでは、既存の平滑化ベースの手法を凌駕し、かつCMA-ESのような共分散行列の保持を必要とする共分散適応型の手法よりも計算負荷が低い代替手段を提供している。著者らは、パワー変換とホモトピー型の減衰の組み合わせが、困難なブラックボックス最適化タスクに対して、強力な理論的収束保証と優れた実証結果の両方を提供すると結論付けている。