A Data-dependent Early Stopping Rule using Rademacher Complexity with L1-norm

技術要約：L1ノルムを用いたラデマッハー複雑度によるデータ依存的な早期終了則

問題提起
ニューラルネットワークの訓練には、訓練データへの適合と、未知の入力に対する堅牢な性能（汎化性能）との間のトレードオフを調整する必要があります。これは、経験的リスク（$L_S$）と期待ポピュレーション・リスク（$L_D$）の差によって決定されます。汎化損失（$L_G$）は、これら二つの差として定義されます。勾配降下法（GD）の過程において、$L_S$は通常減少しますが、$L_G$は増加するため、「バイアス・バリアンス」のトレードオフが生じます。早期終了（アーリーストッピング）の目的は、和 $L_S + L_2$ を最小化する最適なタイミング $t^*$ で訓練を停止することです。

古典的には、$t^*$ は別途用意したテストセット（$S_{test}$）を監視することによって数値的に推定されます。あるいは、ランダム行列理論（RMT）を用いた解析的なアプローチも存在しますが、それらはガウス分布に従うデータや、データ共分散行列の特定の固有値分布（例：マルチェンコ・パストゥル分布）といった、強い確率論的な仮定に依存することがよくあります。本論文は、別途のテストセットや制限的な分布の仮定を必要としない、解析的な早期終了則の必要性に対処しています。

手法
著者らは、勾配降下を行わずに最適な停止時間を推定するための、**ラデマッハー複雑度（RC）**に基づいた解析的なフレームメントを提案しています。この手法は線形モデルおよび線形回帰に焦点を当てており、「線形プロービング」を通じた非線形ネットワークへの拡張も行っています。

1. L1ノルム定式化： 既存の多くのRC境界がL2ノルムを利用しているのに対し、本研究ではL1ノルムを用いてラデマッハー複雑度を表現しています。このL1ノルムの選択は、汎化誤差境界からデータ依存の定数 $M$（損失の上限）を排除することを目的としています。一般的な $L_p$ ノルム境界において $p=1$ と設定することで、著者らは、明示的な $M$ への依存を回避し、経験的誤差ベクトルとモデルノルムのみに依存するポピュレーション損失の上限を導出しています。
2. 勾配フローのダイナミクス： この問題は、連続時間における勾配フロー（GF）を用いてモデル化されています。著者らは、訓練誤差ベクトル $v(t)$ とモデルパラメータ $a(t)$ のダイナミクスを分析しています。ポピュレーション損失の上限（$L^*_D(t)$ と表記）は、経験的損失が減少するにつれて最初は減少し、その後モデルノルムが増大するにつれて増加するという、「U字型」の挙動を示すことが示されています。
3. 解析的な停止基準（$t^+$）： 本研究の核心的な貢献は、すべての $t \leq s$ において $L^*_D(t)$ が減少することを保証する、データ依存の基準 $C(s)$ の導出です。
   • 著者らは、データ共分散行列の固有値を「情報を持つもの（大きい固有値）」と「ノイズとなるもの（小さい固有値）」の集合に分解しています。
   • これら固有値と誤差のダイナミクスを含む関数 $\Phi(t)$ を定義しています。
   • 停止時間 $t^+$ は、すべての $t \in [0, s)$ に対して $\Phi(t) > 0$ であるような時間 $s$ の上限として定義されます。
   • 数学的には、$t^+$ は $\Phi(t)$ がゼロを横切る最初の時刻です。$t^+$ は真の最適時間 $t^*$ の下限推定値であること（すなわち $t^+ \leq t^*$）が証明されています。特定の条件（例：真の最小値が最初の符号不変区間内にある場合）において、$t^+ = t^*$ となります。
4. 近似： 論文では、単純な近似式 $t^+_{approx} \approx \frac{1}{\lambda_1} \ln \frac{\Gamma(0)}{\Omega(0)}$ を提供しています。これは、RMTの文献で見られる信号対雑音比（SNR）の定式化に似ていますが、ここでは確率的な仮定なしに導出されています。

主な貢献

• 分布フリーな解析的推定： 本論文は、ガウス分布に従うデータやデータの固有値分布に関する制限的な仮定を置くことなく、最適な早期終了時間を解析的に推定する方法を導入しています。
• L1ノルムの利点： 著者らは、L1ノルムを用いたラデマッハー複雑度が、L2ノルムを用いたアプローチよりも、数値的な最適値（$t_{test}$）に有意に近い停止時間の推定値（$t^+$）を与えることを、理論的および数値的に示しています。
• アンダーパラメトリゼーションへの焦点： この手法は、特に「ベニグ・オーバーフィッティング（有益な過学習）」や「エポックごとの二重降下（double descent）」が顕著ではない、アンダーパラメトリゼーション領域（$m \leq n$）向けに設計されています。
• 線形プロービングへの適用： 理論は線形モデルに対して導出されていますが、著者らは隠れ層を凍結して出力層のみを訓練する（線形プロービング）ことで、非線形ニューラルネットワーク（具体的にはMNIST分類）に対してもこの結果を成功裏に適用しています。

結果
著者らは、いくつかの例を通じて手法を検証しています。

• 合成ガウスデータ： 二値分類タスクにおいて、異なるサンプルサイズ（$n=512$ および $n=16384$）を用い、解析的な推定値 $t^+$ は、前者のケースでは真の最適時間 $t^*$ と正確に一致し、後者のケースではタイトな下限を提供しました。L1ベースの推定値は、L2ベースの推定値よりも一貫してテストセットの最適値に近い結果となりました。
• MNIST分類（3-5 および 0-1）： 線形プロービングを用いた4層ReLUネットワークを使用し、本手法は停止時間を正確に予測しました。3-5分類では、$t^+ = 342$ であり、これは数値的最適値 $t^* = 357$ およびテストセット最適値 $t_{test} = 356$ に近い値でした。0-1分類では、$t^+ = 415$ であり、$t^* = 415$ と一致し、$t_{test} = 418$ に近い値となりました。
• 停止の有用性： テストされたすべてのケースにおいて、推定された停止時間における損失は、無限の訓練時間における損失よりも低くなっており（$L^*_D(t^+) < L^*_D(\infty)$）、早期終了が有益であることを確認しました。これにより、「ベニグ・オーバーフィッティング」の領域を回避できることが示されました。
• 堅牢性： 本手法は、異なるデータ分布（ガウス、一様、パレート）においても良好に機能し、パラメータに対するサンプル数の比率（$n/m$）が増加するにつれて性能が向上しました。

意義と主張
本論文の主要な意義は、別途の検証セットやデータの分布に関する制限的な確率論的仮定を必要とせずに機能する、データ依存の解析的な早期終了則を提供することにあると主張しています。ラデマッハー複雑度をL1ノルムを用いて活用することで、著者らは、線形モデル（および線形プロービングを通じた特定の非線形ネットワーク）の訓練をいつ停止すべきかを判断し、汎化誤差を最小化するための実用的なツールを提供しています。著者らは、本手法はアンダーパラメトリゼーションモデルには有効であるものの、「ベニグ・オーバーフィッティング」が発生するオーバーパラメトリゼーション領域を対象としたものではないことを謙虚に述べています。また、今後の研究方向として、完全な非線形モデルへの直接的な適用、ベクトル出力への対応、および入力データのランダムノイズの扱いを挙げています。