New Insight of Variance reduce in Zero-Order Hard-Thresholding: Mitigating Gradient Error and Expansivity Contradictions

技術的サマリー：ゼロ次ハードしきい値における分散低減の新たな洞察

問題定義
本論文は、高次元機械学習タスクにおけるスパース学習の達成に不可欠な$\ell_0$制約付き最適化問題の解決という課題に取り組む。具体的な問題は、$\|\theta\|_0 \leq k$の制約の下で、正則化された経験的リスク$F(\theta) = \frac{1}{n}\sum_{i=1}^n f_i(\theta)$を最小化する形式で定式化される。ハードしきい値反復アルゴリズムは$\ell_0$制約に対して効果的であるが、伝統的には真の勾配へのアクセスを必要とする。多くの現代のシナリオ、すなわちバンディット問題、ブラックボックス敵対的攻撃、強化学習などでは、勾配にアクセスできないため、関数評価に依存するゼロ次（ZO）最適化手法の使用が必要となる。

この設定における既存の最先端アルゴリズムである確率的ゼロ次ハードしきい値法（SZOHT）は、重大な限界を有している。著者らは、ZO 勾配推定量の偏差（誤差）とハードしきい値演算子の拡張性（非非拡張性）との間に、本質的な矛盾が存在することを特定した。収束を確保するため、SZOHT は勾配推定に使用されるランダム方向の数（$q$）とスパース性レベル（$k$）に対して厳格な条件を課す。これらの条件は実用的な応用にはしばしば過度に制限的であり、アルゴリズムの実用性を制限している。

手法
本論文は、ZO 勾配とハードしきい値との間の矛盾を解決する新たな視点として、分散低減に焦点を当てることを提案する。著者らは、この矛盾は勾配推定そのものの誤差ではなく、ハードしきい値演算子と勾配推定の分散との間にあると主張する。

これに対処するため、本論文はpM-SZHT（p-Memorization Stochastic Zeroth-Order Hard-Thresholding）と呼ばれる汎用フレームワークを導入する。このフレームワークは、SAGA や SVRG などの一次分散低減手法と同様に、分散を低減するために歴史的勾配を利用するが、ZO 設定に適応させたものである。中核的な構成要素は以下の通りである：

1. 一般化された反復式：アルゴリズムは、$\theta^{(r+1)} = H_k(\theta^{(r)} - \eta \hat{g}^{(r)}(\theta^{(r)}))$という更新則に従う。ここで、$\hat{g}^{(r)}$は分散低減を組み込んだ一般化された勾配推定量である。
2. p-Memorization：このフレームワークは、各反復で勾配推定量のランダムな部分集合を更新するメモリ機構を採用し、アルゴリズムが歴史的情報を活用して ZO 推定量を安定化できるようにする。
3. 具体的なアルゴリズム：このフレームワーク内で、著者らはVR-SZHT（SVRG の ZO 適応版）やSARAH-SZHT（SARAH の ZO 適応版）など、具体的なアルゴリズムを具体化する。

理論的解析
本論文は、制限付き強凸性（RSC）および制限付き強滑らかさ（RSS）という標準的なスパース学習の仮定の下で、包括的な収束解析を提供する。

• 矛盾の緩和：解析は、分散低減を使用することで、収束に必要なランダム方向の数（$q$）に対する厳密な依存関係を排除できることを示している。SZOHT では、$q$は$k$に対する特定の境界を満たすのに十分な大きさでなければならないのに対し、提案手法では（学習率などの他のパラメータが適切に選択されている限り）、任意の$q > 0$に対して収束が保証される。
• 収束速度：理論的結果は、提案アルゴリズムが SZOHT に比べて改善された収束速度を達成することを示している。具体的には、VR-SZHT のクエリ複雑度は$O([n + \frac{\kappa^3}{\kappa^2+1}] \log(1/\epsilon))$と導出され、特に条件数$\kappa$が大きい場合、SZOHT の$O((k + d/s^2)\kappa^2 \log(1/\epsilon))$という複雑度に対して大幅な改善を表している。
• $q$からの独立性：重要な理論的発見として、分散低減は収束条件をランダム方向の数から切り離し、より柔軟なパラメータ選択を可能にすることである。

実験結果
著者らは、以下の 2 つの主要なタスクにおいて手法を検証した：

1. リッジ回帰：合成データを用いて、提案された分散低減アルゴリズム（VR-SZHT、SAGA-SZHT、SARAH-SZHT）は、バニラ SZOHT およびフル勾配 ZOHT（FGZOHT）を一貫して上回った。これらは、より少ないハードしきい値操作（NHT）でより低い関数値を達成し、競争力のあるゼロ次オラクル呼び出し（IZO）を実現した。
2. ブラックボックス敵対的攻撃：これらの手法は、ブラックボックス分類器に対する CIFAR-10 データセット上のスパースな汎用敵対的摂動の生成に応用された。結果は、分散低減手法、特に SARAH-SZHT と SAGA-SZHT が、SZOHT に比べて高い攻撃成功率と低い損失値を達成することを示している。例えば、SARAH-SZHT は「飛行機」クラスの 10 枚の画像のうち 7 枚に成功して攻撃し、SZOHT を上回った。

意義と主張
本論文は、分散低減に対する「新たな洞察」を提供し、それを単なる高速化メカニズムではなく、ZO 推定量とハードしきい値演算子間の固有の矛盾を緩和するための不可欠なツールとして位置づけることを主張する。この研究の意義は以下の点にある：

• 制約の緩和：SZOHT に見られるランダム方向の数（$q$）に対する禁止的な制限を排除し、ZO ハードしきい値をより広範な実世界の問題に対して実用的にする。
• 汎用フレームワーク：さまざまな分散低減 ZO 手法を包含する一般的な解析フレームワーク（pM-SZHT）を確立し、統一的な理論的理解を提供する。
• 実用性：敵対的攻撃と回帰に関する実験結果は、これらの手法がスパース制約を維持しつつ、最先端の ZO アルゴリズムと比較して競争力のある、あるいは優れた性能を達成できることを示している。

著者らは、このアプローチが既存のスパースゼロ次最適化アルゴリズムを効果的に強化し、勾配にアクセスできないシナリオに対して、より柔軟で回復力のある解決策を提供すると結論付けている。