Proximal Projection for Doubly Sparse Regularized Models

技術的概要：二重スパース正則化モデルのための近傍射影

問題提起
予測変数の数（$p$）がサンプルサイズ（$n$）を上回る高次元回帰設定において、標準的な最小二乗法（OLS）は特異性と多重共線性により失敗する。LASSO（$l_1$ペナルティ）や Ridge（$l_2$ペナルティ）などの正則化法はスパース性と安定性を扱うが、予測変数間の構造的関係を見落とす傾向がある。予測変数がガウスグラフィカルモデルで表現できる場合、この構造を利用することで推定が改善される。

既存のアプローチ、例えばグラフ構造を組み込んだスパース回帰（SRIG）およびその二重スパース拡張（DSRIG）は、係数ベクトル $\beta$ をノードの寄与に対応する潜在変数に分解し、これらの潜在変数に対して正則化を適用する。しかし、グループ間およびグループ内の両方でスパース性を実現する「二重スパース性」を達成する DSRIG モデルは、重なり合うグループを処理するために予測変数の複製に依存している。このアプローチは、最適化問題の次元を大幅に増加させるため、高次元データや密なグラフに対して計算量が膨大となり、実行不可能になる。さらに、DSRIG はグループ間およびグループ内のスパース性のバランスを取るために 2 つのパラメータ（$\lambda$ と $\xi$）の調整を必要とし、最適解の探索を複雑化している。

手法
著者は、**グラフ構造を組み込んだスパース重なりグループ LASSO（SGLIG）**モデルを提案する。このモデルは、二重スパース性を維持しつつ計算複雑性と調整パラメータの数を削減するために、DSRIG フレームワークを再パラメータ化している。

1. モデル定式化:
   SGLIG モデルは、以下の目的関数を最小化する：
   $$\min_{\beta, V^{(1)}, \dots, V^{(p)}} \frac{1}{2n}\|Y - X\beta\|_2^2 + \lambda^* \sum_{i=1}^p \left( \alpha \tau_i \|V^{(i)}\|_2 + (1-\alpha) \frac{1}{\sqrt{d_i}} \|V^{(i)}\|_1 \right)$$
   ここで、$\beta = \sum V^{(i)}$、$V^{(i)}$ は予測変数 $i$ の寄与を表し、$d_i$ は近傍の次数であり、$\alpha \in [0, 1]$ は $l_2$（グループ）と $l_1$（グループ内）のペナルティ間のトレードオフを制御する。DSRIG と異なり、SGLIG は単一の調整パラメータ $\alpha$ を使用する（$\lambda^*$ は $\lambda_{max}$ に基づく定数として固定される）。これにより、最適化のグリッドサーチが簡素化される。

2. 二重射影近傍アルゴリズム:
   SGLIG の目的関数を最適化するために、著者は FISTA（Fast Iterative Shrinkage-Thresholding Algorithm）に基づいた二重射影近傍アルゴリズムを開発した。

   • アクティブグループ戦略: アルゴリズムは、現在の勾配ステップに基づいてアクティブなグループ集合 $\hat{G}_m$ を特定する。
   • 交差点への射影: 予測変数を複製する代わりに、アルゴリズムは $l_2$ ノルム球と $l_\infty$ ノルム球で定義される凸集合の交差点に射影することで近傍演算子を計算する。
   • 2 段階射影: 射影は逐次的に計算される。まずグループ内スパース性（$l_1$/$l_\infty$）のためのソフトスレッショルディングを適用し、次にグループ間スパース性（$l_2$）のためのグループソフトスレッショルディングを適用する。これは、アクティブセット戦略に対してより効率的であると著者が主張する Parallel Dykstra 型アルゴリズムではなく、射影法（POCS）の連続的な合成を用いて実装されている。

3. 理論的性質:
   本論文は、最適分解、制限付き強凸性（RSC）、および重み $\tau_i$ とノード次数に関する特定の仮定の下で、SGLIG 推定量の有限サンプル誤差限界を導出した。さらに、$n \to \infty$ かつ $p$ が固定の条件下での推定量の漸近正規性を証明し、追加された $l_1$ ペナルティにもかかわらず SRIG モデルと整合性があることを示した。

主要な貢献

• アルゴリズム的革新: 予測変数の複製を回避する新しい二重射影近傍アルゴリズムの開発。この手法は凸集合の交差点への射影を反復的に計算し、高次元および密なグラフ構造における計算リソースを節約する。
• モデルの効率性: SGLIG モデルは、1 つの調整パラメータ（$\alpha$）のみで二重スパース性を達成し、2 つのパラメータを必要とする DSRIG に比べてハイパーパラメータ選択の計算負担を軽減する。
• 理論的保証: SGLIG 推定量に対する有限サンプル誤差限界の導出と漸近正規性の証明により、標準的な仮定の下での統計的妥当性を確立した。
• 実証的検証: 5 つの異なるグラフ構造（2 クラス、二部、ランダム、ブロック、バンド）を持つシミュレーションデータと、2 つの実世界データセット（血液脳関門およびアルツハイマー病神経画像イニシアチブ）による包括的な評価。

結果

• シミュレーション研究:

  • 精度: DSRIG モデルは一般的に最小二乗誤差（MSE）と $l_2$ 距離において最も低い値を達成した。しかし、SGLIG モデルは競争力のある性能を示し、DSRIG の精度にほぼ匹敵しつつ、単一スパース性の SRIG モデルを大幅に上回ることが多かった。
  • 効率性: SGLIG モデルは、DSRIG に比べて計算時間の大幅な削減を示した。高次元のシナリオ（例：800 個の予測変数）において、DSRIG は 2,900 秒以上を要したが、SGLIG は約 60 秒、SRIG は 40 秒で済んだ。SGLIG は SRIG の速度と DSRIG の精度の間のギャップを効果的に埋めている。
  • グラフ感度: SGLIG は、線形接続構造のためグループ内スパース性があまり有益ではなかった「バンド」グラフを除き、さまざまなグラフトポロジーに対して頑健に機能した。

• 実世界データ:

  • 血液脳関門データセットにおいて、SGLIG は 3 つのモデルの中で最低の MSE を達成し、計算時間は SRIG と同等、DSRIG よりも大幅に短かった。
  • 変数選択分析により、SGLIG と DSRIG（どちらも二重スパース）は粒子電荷に関連する変数を選択したのに対し、SRIG は表面積の測定値に焦点を当てていたことが示された。これは、二重スパース性が異なる構造的ニュアンスを捉えていることを示唆している。

意義と主張
本論文は、SGLIG モデルがグラフ構造を有する高次元回帰に対する実用的な妥協案を提供すると主張している。予測変数の複製を新しい近傍射影技術に置き換えることで、著者は二重スパース性の恩恵を損なうことなく計算リソースを節約できると述べている。結果は、SGLIG が他の単一または二重スパースなグラフ回帰モデルに対して安定した性能を示すことを示唆しており、DSRIG が計算的に実行不可能なシナリオにおける viable な代替手段となっている。著者は、その実装が密な予測変数グラフを持つ高次元データに対して特に有利であると強調している。