Spectral conjugate gradient projection methods for large-scale monotone equations without Lipschitz continuity

技術的概要：大規模単調方程式に対するスペクトル共役勾配射影法

問題定義
本論文は、連続な単調写像 $G: \mathbb{R}^n \to \mathbb{R}^n$ および非空かつ閉かつ凸な集合 $\Gamma \subset \mathbb{R}^n$ に対して、$G(x) = 0$ となるベクトル $x \in \Gamma$ を求める問題を扱っている。この定式化は、変分不等式問題、相補性問題、化学平衡計算、圧縮センシング、正則化ロジスティック回帰を含む。ニュートン型手法は微分可能な $G$ に対して局所的な高速収束を提供するが、$O(n^2)$ の記憶容量要件とヤコビアンの計算が必要となるため、大規模問題には実用的ではない。共役勾配（CG）法は、関数評価のみを必要とし、$O(n)$ の記憶容量で済むため、大規模設定において好まれる。しかし、CG 法を制約付き設定に拡張するには通常、射影技術に依存しており、既存の手法は $G$ のリプシッツ連続性を必要とするか、あるいは最適でない収束率に悩まされることが多い。

手法
著者は、確立された共役勾配フレームワークに適応的スペクトルパラメータ $\lambda_k$ を統合する、2 つの導関数不要の射影法を提案する。両手法とも、ソロドフ・スヴァイター射影技術を採用しており、降下方向の計算、試行点を生成するための線探索、$G$ の単調性に基づいた分離超平面の構築、および現在の反復点のこの超平面への射影を含む。

1. GMOPCGM（一般化修正最適ペリー共役勾配法）：
   この手法は、Sabi'u らによる修正最適ペリー共役勾配法（MOPCGM）を一般化したものである。探索方向は、スケーリングパラメータが適応的スペクトルパラメータ $\lambda_k$ に置き換えられた修正最適ペリー行列から導出される。パラメータ $\lambda_k$ は $[\alpha_{\min}, \alpha_{\max}]$ の範囲に有界であり、局所的な曲率（$s_{k-1}$ および $v_{k-1}$）に基づくバルジライ・ボロワイン型スペクトル比を用いて更新される。得られた探索方向は、線探索に依存しない十分な降下条件を満たす。

2. GCGPM（一般化共役勾配射影法）：
   この手法は、Hager–Zhang パラメータに基づく Zheng らの CGPM を一般化したものである。著者は、更新式にスペクトル Dai–Liao パラメータ $\lambda_k$ を導入する。GMOPCGM と同様に、スペクトルパラメータは問題の局所幾何学に適応する。探索方向は、十分な降下を確保するように構成される。

主要な貢献

• 新しい探索方向の導出： 本論文は、スペクトルパラメータ $\lambda_k$ を通じて既存の MOPCGM および CGPM フレームワークを一般化する、2 つの新しい探索方向を導出した。
• 線探索に依存しない十分な降下： 提案された 2 つの手法の両方が、線探索戦略に依存せず成立する十分な降下条件（$G_k^T p_k \leq -c \|G_k\|^2$）を満たすことが証明された。
• より弱い仮定における大域収束：
  • GMOPCGM については、仮定 A1（解集合が非空）および A2（単調性）のみのもとで大域収束が確立された。重要なのは、この結果が $G$ のリプシッツ連続性を必要としない点である。
  • GCGPM については、リプシッツ連続性を含む標準的な仮定 A1–A3 のもとで大域収束が証明された。
• 実用的有効性： 最大 120,000 次元の 18 個のベンチマーク問題、ならびに圧縮センシングおよび正則化ロジスティック回帰の応用において、これらの手法がテストされた。

数値結果
著者は、GMOPCGM および GCGPM を、既存の 3 つの手法（MOPCGM、CGPM、STTDFPM）と比較する広範な数値実験を実施した。

• ベンチマーク問題： 5,400 回の実行（18 問題、6 次元、10 初期点）全体において、GCGPM は最高収束率（96.9%）および最中央値反復回数（10 回）と関数評価数（52 回）を達成した。GMOPCGM は 93.0% の事例で収束し、中央値反復回数は 28 回であり、その前身である MOPCGM（160 回）と比較して大幅な改善を示した。
• 圧縮センシング： $\ell_1$ 正則化信号復元タスクにおいて、提案された 2 つの手法は 240 件のテスト事例すべてで収束した。GCGPM および GMOPCGM は、20 事例で失敗した MOPCGM に比べて、反復回数と CPU 時間を大幅に削減した。すべての手法は、信号復元において比較可能な平均二乗誤差（MSE）を達成した。
• 正則化ロジスティック回帰： 実世界の二値分類データセットにおいて、提案された 2 つの手法は 60 事例すべてで収束した。GMOPCGM は中央値反復回数を 2,447 回（MOPCGM）から 313 回に削減し、非線形単調方程式に対するスペクトル一般化の利点を示した。GCGPM は最も効率的で、中央値反復回数は 184 回であった。

意義と主張
本論文は、適応的スペクトルパラメータを共役勾配射影フレームワークに統合することが、大規模単調方程式を解くための堅牢なアプローチを提供すると主張している。主要な理論的意義は、単調方程式に対する導関数不要手法の分析における一般的なボトルネックであるリプシッツ連続性の要件を除去した、GMOPCGM に対する収束証明にある。実用的には、結果はスペクトル一般化が収束速度と計算コストの面でベース手法に対して一貫して性能を向上させることを示しており、提案されたアルゴリズムが信号処理や機械学習における高次元応用に適していることを示している。著者は、今後の研究として、GCGPM の収束解析を擬単調設定に拡張し、慣性加速技術を探求することができると指摘している。