Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise

技術的概要：重尾ノイズを伴うゼロ次非凸非滑らか最適化

問題定式化
本論文は、以下の制約なし確率的最適化問題を扱う：
$$\min_{x \in \mathbb{R}^d} f(x) = \mathbb{E}_{\xi \sim P}[F(x; \xi)]$$
ここで、目的関数 $f$ は非凸かつ非滑らかであるが、リプシッツ連続である。設定はゼロ次であり、アルゴリズムは勾配ではなく、ノイズを含む関数評価 $F(x; \xi)$ のみへのアクセスを有する。

既存の研究からの重要な転換点は、ノイズの仮定にある。多くの既存の解析は有界分散仮定（2 次モーメント）に依存しているが、本論文は重尾ノイズの仮定の下で動作する。具体的には、確率的成分関数のリプシッツ定数 $L(\xi)$ は、有界な $p$ 次モーメント条件を満たす：
$$\mathbb{E}[L(\xi)^p] \leq L^p$$
ここで $p \in (1, 2]$ である。$p < 2$ の場合、分散は有界でない可能性があり、これは深層ニューラルネットワークの学習や強化学習などの実世界の機械学習アプリケーションで一般的に観察される重尾分布（例：レヴィ $\alpha$ 安定分布）を特徴付ける。

手法：ZOCOON アルゴリズム
著者らは、**ゼロ次クリップド・オンライン・トゥ・非凸（ZOCOON）**アルゴリズムを提案する。この手法は 3 つの中核的要素を統合している：

1. オンライン・トゥ・非凸変換フレームワーク：Cutkosky ら [9] によって確立され、Kornowski と Shamir [25] によって拡張されたフレームワークに基づき、アルゴリズムはオンライン学習問題を非凸最適化ソルバーに変換する。これには、定常点を見つけるためにラウンド全体で更新のシーケンスを実行することが含まれる。
2. 2 点確率勾配推定量：勾配が利用できないため、アルゴリズムは滑らかな代理関数 $f_{\delta'}(x)$ に基づくゼロ次推定量を使用する。点 $x$ と単位球面上のランダムな方向 $w$ に対して、推定量は以下の通りである：
   $$\hat{g}(x; w, \xi) = \frac{d}{2\delta'} (F(x + \delta'w; \xi) - F(x - \delta'w; \xi))w$$
   これは、滑らかな関数の勾配の不偏推定値を提供する。
3. 勾配クリッピング：重尾ノイズの影響を軽減するため、アルゴリズムは勾配推定量にクリッピング演算子を組み込む。更新ステップでは $\hat{g}_{clipped} = \text{clip}(\hat{g}, \tau)$ を使用し、ここで $\tau$ は閾値パラメータである。これにより、最適化プロセスを不安定化させる可能性のある大きくノイズの多い勾配を防ぐ。

アルゴリズムはリスタートを伴うエポックで動作し、収束保証を確保するために平均化された反復点の集合から一様にランダムな点を出力する。

主要な貢献と理論的結果
本論文は、Goldstein $\delta$-部分微分を通じて定義される非滑らか関数に対する近似定常性の洗練された概念である$(\delta, \epsilon)$-Goldstein 定常点の発見に対する理論的保証を確立する。

• 収束複雑性：ZOCOON アルゴリズムは、確率的ゼロ次オラクル複雑性 $O\left( d^{\frac{p}{2(p-1)}} \delta^{-1} \epsilon^{-\frac{2p-1}{p-1}} \right)$ で $(\delta, \epsilon)$-Goldstein 定常点に到達する。この結果は、期待値と高確率の両方で成り立つ。
• 次元依存性：次元 $d$ への依存性は、凸非滑らか設定における確率的ゼロ次最適化の既知の最良の結果と一致する。
• 精度依存性：精度パラメータ $\delta$ と $\epsilon$ への依存性は、重尾ノイズ下での非凸非滑らか問題に対する既知の最良の確率的一次アルゴリズムと一致する。
• 滑らか拡張：結果は自然に滑らかな設定に拡張される。$\delta = \epsilon/H$（ここで $H$ は滑らかさ定数）と設定することで、この手法は滑らかな非凸最適化に対する最適な確率的一次手法と複雑性が一致する $\epsilon$-定常点に到達する。

実験的検証
数値実験は、人工的に追加された重尾ノイズ（パレート分布）を伴う実世界のデータセット（a9a, covtype, w8a）を使用した非凸正則化 SVM 問題に対して実施された。

• ベースライン：ZOCOON は GFM [26]、GFM+ [5]、および ZOO2N [25] と比較された。
• 知見：ZOCOON と ZOO2N は、GFM および GFM+ よりも著しく速く収束した。ZOCOON はほとんどのデータセットで ZOO2N よりも安定した性能を示し、重尾ノイズの処理におけるクリッピングメカニズムの有効性を検証した。

意義と主張
本論文は、文献における重要なギャップを埋めると主張している。すなわち、重尾ノイズは実務において一般的であるが、非凸非滑らか最適化に対する既存のゼロ次手法は、有界分散仮定または凸設定に限定されていた。

• 史上初：ZOCOON は、重尾ノイズ下での非凸非滑らか最適化に対する最初の効率的な確率的ゼロ次アルゴリズムとして提示される。
• 最適性：著者らは、$L$、$\delta$、および $\epsilon$ への依存性が、この問題クラスに対して最近確立された下限と一致することを指摘しており、精度パラメータに関してこの手法がほぼ最適であることを示唆している。
• 頑健性：この研究は、一次手法で一般的な手法である勾配クリッピングが、次元依存複雑性を犠牲にすることなく、有界でない分散を処理するためにゼロ次フレームワークに成功裏に適応できることを実証している。

本論文は、次元依存性が最適かどうか、およびフレームワークを制約付き最適化問題に拡張できるかどうかという未解決の問題を認めて結論付けている。