技術要約：最小二乗回帰における早期停止による正則化

問題提起

本論文は、機械学習モデル、特に線形回帰の文脈において、早期停止（early stopping）がパラメータおよび汎化能力に与える影響を理解するという根本的な課題に取り組んでいる。早期停止は広く用いられている正則化手法であるが、その理論的特性、特に任意の学習率スケジュールやデータ分布を用いた離散的なフルバッチ勾配降下法における性質については、完全には解明されていない。

既存の文献は、連続時間勾配フローのダイナミクスや特徴行列に対するガウス仮定など、強い仮定に依存することが多い。こうしたアプローチでは、実用的な非定数学習率スケジュール下での最適な停止時間を定量化することや、離散的な設定における「グロッキング（grokking）」（モデルが過学習した後に汎化が進む現象）を説明することが困難である。さらに、早期停止と明示的な $L_2$（リッジ）正則化との正確な関係、および早期停止が有益となる条件と有害となる条件の境界についても、限定的な分布仮定を置かずに、より厳密な特徴付けが必要とされている。

手法

著者らは、連続時間勾配フロー近似を避け、線形回帰におけるフルバッチ勾配降下法の離散ダイナミクスを分析している。核心となる手法上の貢献は、パラメータの軌跡 $\beta_k$ に関する正確かつ閉形式の式を導出したことである。

主な手法構成要素は以下の通りである：

1. スペクトル分解: 分析はサンプル共分散行列 $X^T X$ の固有基底を用いて行われる。著者らは、特定の固有値 $\zeta$ に対する学習率スケジュール $\{\eta_i\}$ の累積効果を捉える関数 $\phi(k; \zeta, \{\eta_i\})$ を定義している。
2. 正確な軌跡の定式化: この関数を用いることで、任意のデータ行列 $X$、任意の学習率スケジュール、および任意の初期値に対して成立する $\beta_k$ の明示的な公式を導出している。この公式は、誤差を信号成分（初期値と真のパラメータに依存）とノイズ成分（残差に依存）に分解する。
3. リスク分析: 期待過剰リスクは、ノイズに関する期待値を取り、さらに球状事前分布の仮定の下で信号に関する期待値を取ることによって分析される。著者らは、反復回数を（仮定2を通じて連続変数として扱うことで）反復回数に関して微分し、臨界点を特定している。
4. 等価性の証明: 早期停止された解と、一般化リッジ回帰問題の解との間の数学的な等価性を証明し、正則化効果の直接的な比較を可能にしている。

主要な貢献

1. 離散ダイナミクスの正確な軌跡

本論文は、カーネルリッジ回帰の離散ダイナミクスに関する正確な公式を与える命題1を提示している。先行研究とは異なり、これらの公式はデータ分布、学習率スケジュール、またはノイズ分布に関するいかなる仮定も設けていない。著者らは、定数、多項式減衰、定数加算減衰、および指数減衰（ガンマ関数と $q$-ポッホマー記号を使用）を含む、様々な一般的なスケジュールに対する $\phi$ の閉形式の表現を提供している。

2. 一般化リッジ回帰への等価性

著者らは、一般的なデータと任意の学習率スケジュールにおいて、$T$ 回の反復（$\mu=0$）の後に得られる解が、一般化リッジ回帰問題の最小ノルム解と等価であることを示す定理5を証明している。この一般化された問題における正則化行列 $D$ は、学習率スケジュールと停止時間によって明示的に決定される。
逆に、定理6は、標準的なリッジ回帰問題の任意の最小ノルム解が、サンプル共分散行列の各固有空間に対して異なる学習率を割り当てることで、早期停止を通じて得られることを示している。

3. 有益性と有害性の条件

早期停止が汎化性能を向上させるための十分条件を確立している：

• 定理 8（有益な場合）: 学習率スケジュールが「収縮因子（shrinkage factor）」$\phi(k)$ を十分に速く減衰させ、$\phi(k)/\phi(0)$ の極限が信号対雑音比によって決定される閾値よりも小さくなる場合、早期停止は有益である。これは、累積ステップサイズが発散する定数、線形減衰、およびその他のスケジュールにおいて成立する。
• 定理 9（有益でない場合）: 学習率が速すぎる場合（例：高速な多項式減衰や指数減衰）、収縮因子が必要な閾値に達しないため、早期停止は有益ではない。この場合、さらなる訓練によってリスクは減少し続ける。
• 定理 10（リッジ正則化）: これらの条件は、明示的なリッジ正則化（$\mu > 0$）が存在する場合にも拡張される。重要な知見は、明示的な正則化パラメータ $\mu$ が臨界値（$\mu \ge \tau^2 / (n\sigma^2)$）を超える場合、早期停止による追加の利益が得られないことである。

4. 最適停止時間の推定

著者らは、累積学習率予算 $\sum \eta_i$ に基づく最適停止時間の推定式（式31）を提案している。この推定値は、代表的な固有値に対する信号とノイズの最適なバランスに対して、収縮因子を等置することによって導出されている。この推定値は、任意のスペクトルを持つ離散ダイナミクスと非定数学習率の条件下で、勾配フローの領域からの先行研究の結果を一般化したものである。

結果と実証的検証

理論的な知見は、合成データおよび実世界のデータセット（MNISTおよびCIFAR10）を用いた実験を通じて検証されている。

• 推定の精度: 提案された停止時間の推定値（式31）は、様々な学習率スケジュール（定数、多項式、線形、指数、コサインアニーリング、およびランダム）において、経験的に観察された最適停止時間に密接に一致している。
• レジーム依存性: 実験により、明示的なリッジパラメータ $\mu$ が最適なリッジパラメータ $\mu^*$ 未満である場合に早期停止が有益となり、$\mu \ge \mu^*$ の場合には有害（または不要）になるという理論的予測が確認された。
• スケジュールの感度: 最適値が発生する反復回数は学習率スケジュールによって大きく異なるが、累積的な学習率の予算が、最適な停止点に対するロバストな予測因子として機能することが実験で示された。
• グロッキング: 本分析は、多くの一般的な学習率スケジュール（累積ステップサイズが発散するもの）において、線形モデルは「グロッキング」（過学習後の遅れた汎化）を示さず、代わりに早期停止が最適となる古典的なバイアス・バリアンスのトレードオフを示すことを示唆している。

意義と主張

本論文は、線形回帰における早期停止の非漸近的かつ分布に依存しない特徴付けを提供することを主張している。その意義は以下の点にある：

1. 理論と実践の架け橋: 連続時間勾配フローやガウス仮定から離れることで、結果を、任意の学習率スケジュールを持つ実用的な離散訓練シナリオに適用可能にしている。
2. 統一的視点: 早期停止を一般化リッジ正則化と形式的に統一し、早期停止による「暗黙的」な正則化が、数学的に明示的かつデータ依存的な $L_2$ ペナルティと等価であることを示した。
3. 実践的なガイダンス: 真の信号を知る必要はなく、観測可能な量（信号対雑音比、固有値スペクトル、学習率スケジュール）のみに依存する、理論的根拠に基づいた具体的な最適停止時間の推定法を提供している。
4. 限界の明確化: 早期停止がいつ有益で、いつそうでないかを明確に区別しており、特に明示的なリッジ正則化と早期停止の相互作用を強調し、早期停止を無効にする特定の学習率スケジュールを特定している。

著者らは、現在の分析は線形モデルに限定されているものの、このフレームワークは、二層ニューラルネットワークのようなより複雑なモデルを理解するための基礎を提供するものであり、SGDや適応的最適化手法へと結果を拡張するための将来的な方向性を示唆していると結論付けている。