技術要約：オンライン高次元分位点回帰のための適応的反復ハード閾値処理（AIHT）

1. 問題設定

本論文は、データ $(Y_t, X_t)$ が逐次的に到着するストリーミング環境における、オンライン高次元スパース回帰の課題に取り組んでいる。主な目的は、一連の損失関数を最小化することにより、スパースな真の係数ベクトル $\beta^* \in \mathbb{R}^p$ （ここでスパース性レベルは $s_0 \ll p$）を反復的に推定することである。

具体的な焦点は、オンライン分位点回帰にあり、これはチェック損失 $\rho_\tau(u) = u(\tau - \mathbb{1}\{u < 0\})$ を利用する。この設定は、標準的なオンライン凸最適化と比較して、特有の困難さを提示している：

• 非平滑性: 分位点損失は微分不可能であり、劣勾配法を必要とする。
• ロバスト性の要求: 本手法は、標準的な二乗誤差損失が失敗するような、ヘビーテイルなノイズ、不均一分散、および潜在的な分布シフトに対処しなければならない。
• 高次元性: $p$ が有効サンプルサイズを超える場合、経験的なヘッセ行列は特異となり、大域的な強凸性を排除してしまう。スパース性の仮定が必要であるが、これをオンラインで強制することはアルゴリズム上の複雑さをもたらす。

反復ハード閾値処理（IHT）のナイーブな適用（すなわち、毎ステップの確率的勾配更新の後にハード閾値演算子 $H_s$ を適用すること）は、この領域では失敗する。これは、「ワンステップ・エントリー・バリア（一歩での参入障壁）」を生み出し、初期の信号が弱い真の変数が、能動集合に再参入するために十分な勾配質量を蓄積する前に破棄されてしまう。逆に、固定間隔での周期的な閾値処理は、減衰するステップサイズに適応できず、結果としてサポートの発見のための移動が不十分になったり、サポート外のノイズが制御不能に蓄積したりすることを許容してしまう。

2. 手法：適応的反復ハード閾値処理 (AIHT)

著者らは、適応的反復ハード閾値処理 (Adaptive Iterative Hard Thresholding: AIHT) を提案している。これは、確率的勾配の進化とスパース投影を分離するフレームワークである。その核心となる革新は、イテレートの安定性に基づいて学習プロセスを2つの異なるフェーズに分離する適応的スケジュールである。

2.1 コアメカニズム

AIHTはエポック単位で作動する。エポック $j$ 内において：

1. 候補制限更新 (Candidate-Restricted Updates): 全 $p$ 個の座標を更新する代わりに、アルゴリズムは候補集合 $A_j = \hat{S}_j \cup C_j$ に更新を制限する。ここで $\hat{S}_j$ は現在のサポートであり、$C_j$ はサポート外の最大 $m$ 個の劣勾配成分を含む。これにより、サポート外の座標からの「勾配漏れ（gradient leakage）」を抑制する。
2. 遅延閾値処理 (Delayed Thresholding): ハード閾値 $H_s$ は、毎ステップではなく、エポックの終了時のみ適用される。これにより、座標が閾値判定を受ける前に、エポック内の累積ステップサイズ質量 $B_j = \sum_{t \in T_j} \eta_t$ にわたって信号を蓄積することが可能になる。

2.2 二フェーズ適応スケジュール

アルゴリズムは、以下の2つのフェーズ間を動的に遷移する：

• フェーズ I (サポート発見): より大きなステップサイズと、より頻度の低い閾値処理（長いエポック）を使用する。これにより、弱いが情報を持つ座標が成長し、能動集合に参入することを可能にする。
• フェーズ II (局所精緻化): プロジェクション・グラディエント・マッピング統計量の比に基づく安定性診断が、サポートが安定したことを示したときにトリガーされる。アルゴリズムは、より小さなステップサイズ ($O(1/t)$) へと切り替え、閾値処理の頻度を高め（短いエポック）、局所的な曲率を利用して推定量を精緻化する。

2.3 分布シフトへの対処

非定常環境のために、著者らは**再起動可能（restart-enabled）**なAIHTを導入している。これは、隣接ウィンドウ・スコア対照検出器を用いて変化点を特定する。変化点が検出されると、アルゴリズムは「ハード・リスタート」を実行する。すなわち、イテレートをゼロにリセットし、バッファをフラッシュし、新しいサポート構造を再発見するためにフェーズ I に戻る。

3. 理論的貢献

本論文は、制限された曲率および勾配漏れの条件下におけるAIHTの厳密な保証を確立している：

• 円錐不変性 (Cone Invariance): 著者らは、候補制限更新と限定されたエポック質量の下で、イテレートが「膨張したスパース円錐」 $\Gamma_\zeta(c, S)$ 内に留まることを証明している。これにより、サポート外への漏れが制御され、それが周囲次元 $p$ ではなく、スパース性と候補サイズに依存するように制御される。
• 二フェーズ収束:
  • フェーズ I: エラーは、確率的な許容誤差を除いて、エポック質量に対して幾何学的に収縮する。
  • フェーズ II: 精緻化レジームに入ると、アルゴリズムは $O((\log t)/t)$ のエラーレートを達成する。
• リグレット界 (Regret Bounds):
  • スライディングウィンドウ目的関数に対して、総リグレットは $C_I(T_0) + C_{burn} + O(\log T)$ で抑えられる。
  • $T_0$ とバーンイン・コストが $T$ と独立して有界である場合、リグレットは対数的 ($O(\log T)$) であり、非平滑かつ高次元の設定であるにもかかわらず、強凸なオンライン最適化の性能と一致する。
• 動的リグレット (Dynamic Regret): 区分的に定常な設定において、アルゴリズムはセグメントごとの回復を実現し、動的リグレット界はセグメント長に対して対数的に、および変化点の数に対して線形にスケールする。

4. 実証結果

シミュレーションにより、理論的主張と適応的スケジュールの必要性が検証された：

• ロバスト性: AIHTは、特にヘビーテイルなノイズやHuber汚染下において、定常状態の推定誤差に関して、高密度SGDおよびTruncated Gradient (TG) ベースラインを大幅に上回る性能を示した。
• スケジュールの切除実験 (Ablation): 「毎ステップ」および「固定期間」の閾値処理バリアントとの比較により、以下が示された：
  • 毎ステップの閾値処理は、サポートの発見を抑制し、高いエラーを招く。
  • 固定期間の閾値処理は、減衰するステップサイズに適応できず、劣目標な収束を引き起こす。
  • AIHTの適応的なタイミングは、最も低い最終エラーと累積超過損失をもたらす。
• 変化点検出: 非定常実験において、再起動可能なAIHTは変化点を検出し、新しいサポートを回復することに成功したが、再起動を行わないベースラインは持続的な誤差を蓄積した。

5. 意義と主張

本論文は、AIHTがオンライン高次元分位点回帰の特定の困難に対する理論的に裏付けられた解決策を提供すると主張している。その意義は以下の点にある：

1. 発見と精緻化の分離: サポートの発見（フェーズ I）と局所的な精緻化（フェーズ II）を分離することで、ナイーブなハード閾値処理に固有の「エントリー・バリア」問題を克服している。
2. 適応的スケジューリング: 「エポック質量」（累積ステップサイズ）が、投影間の生の反復回数よりも重要なスケジューリング変数であることを示している。
3. 高次元におけるロバスト性: 標準的な凸正則化（Lassoなど）やソフト閾値法がオンラインの状況下で効果的でない、あるいは理論的に解析が困難な場合が多い非平滑・ヘビーテイルな設定へと、ハード閾値処理の適用範囲を拡張している。
4. 厳密な特性化: 二フェーズ収束現象の形式的な特性化を提供し、非平滑・高次元のオンライン学習問題に対して対数的なリグレット保証を確立している。

著者らは、分析は分位点回帰に焦点を当てているものの、アルゴリズムの枠組みはチェック損失に縛られておらず、同様の制限された曲率の仮定の下で他の損失（例：二乗誤差、Huber）にも拡張できる可能性があると述べている。