良い内挿器はどれだけ豊富か — 過剰パラメータ化線形分類の大偏差原理と集中現象

§01 問題設定 — 内挿器の集合と比例的レジーム

機械学習の実践において、モデルのパラメータ数がデータ数を大幅に上回る「過剰パラメータ化」の状況は現代的な標準となっています。このとき、訓練データを完全に暗記する解（内挿解）が無数に存在し得ます。問題は「それらの内挿解は汎化能力においてどのように分布しているか」という本質的な問いです。

本論文の設定を正確に述べます。$d$ 次元実ユークリッド空間 $\mathbb{R}^d$ において、$n$ 個のラベル付きデータ点 $(X_i, y_i)_{i=1}^n$ が与えられます。ここで $X_i \in \mathbb{R}^d$ は特徴ベクトル、$y_i \in \{-1, +1\}$ はクラスラベルです。事前に固定されたマージン値 $\kappa \in \mathbb{R}$（負の値も許容）に対して、すべてのデータ点をマージン $\kappa$ 以上で正しく分類する単位ノルム線形分類器の集合 $S$ を定義します（下記の式を参照）。$\kappa > 0$ のときは正のマージンを要求する制約的な設定ですが、$\kappa \leq 0$ の場合は解の集合 $S$ がより大きくなり、現代の過剰パラメータ化モデルが動作する状況をより忠実に反映します。

解析の骨格となるのは比例的レジームです。$n$ と $d$ をともに無限大に送りながら比率 $\alpha = n/d$ を一定に保つ極限を考えます。$\alpha < 1$ は過剰パラメータ化（パラメータ数がデータ数を上回る状況）に対応します。本論文では $\alpha$ が十分小さい状況を扱っており、これはモデルが訓練データに比べて大幅に過剰に表現される「深い過剰パラメータ化」のレジームに対応します。

データ生成分布については二種類が考察されます。第一はガウス混合モデルで、クラス $y = +1$ に対して $X \sim \mathcal{N}(\mu, I_d)$、クラス $y = -1$ に対して $X \sim \mathcal{N}(-\mu, I_d)$ という形式です。第二はガウス特徴量付きロジスティックモデルで、特徴量 $X$ は標準ガウス分布に従い、ラベルはロジスティック関数を通じて $X$ に依存する形で生成されます。いずれの設定も、確率論的解析を厳密に実行できる構造を持っています。

確率変数として注目するのは、$S$ 上の一様分布から取り出した $\theta$ の汎化誤差 $\text{err}(\theta)$ です。これは、データ分布 $P$ のもとで新しいデータ点 $(X, y)$ に対して $y \langle X, \theta \rangle < 0$ となる確率として定義されます。この確率変数に対して、$d \to \infty$ の極限で大偏差原理が成立することを証明するのが本論文の主目標です。

graph TD
  A[データ分布 P] --> B[n 個のデータ点]
  B --> C[内挿器の集合 S]
  C --> D[一様ランダム抽出 θ]
  D --> E[汎化誤差 err(θ)]
  E --> F[大偏差原理の確立]
  F --> G[集中現象: err ≈ ε*]

§02 先行研究と本論文の位置づけ — ダブルディセントから大偏差原理へ

過剰パラメータ化と汎化の関係は、古典的な統計学では「過学習」として否定的に扱われてきました。モデルパラメータが多すぎれば訓練データに過適合し、汎化能力が失われるというバイアス・分散のトレードオフは、長年の標準的な知見とされてきました。

ところが 2010 年代後半から、この直感と矛盾する現象が理論的に注目されるようになりました。パラメータ数を増やしていくと、一度汎化誤差が上昇（古典的な過学習）するものの、さらにパラメータを増加させると再び汎化誤差が低下するという「ダブルディセント」の現象です。この右側の降下部分において、訓練データを完全に内挿するモデルが良い汎化を達成することが「ベナイン・オーバーフィッティング」です。

Bartlett、Montanari、Wainwright らを中心とした研究グループは、線形回帰モデルにおけるベナイン・オーバーフィッティングの十分条件を確立しました。「最小ノルム解」と呼ばれる特定の内挿解が適切な条件下で汎化することが証明されています。また、Zhang ら（2017）の実証的な研究では、深層ネットワークが正則化なしでも訓練データを完全記憶しつつ汎化できることが観察されており、理論と実験の両側から議論が進んでいます。

しかしながら、これらの先行研究の多くは特定のアルゴリズム（最小ノルム解、擬似逆行列解など）が汎化するかという問いに焦点を当てており、内挿器の集合全体の構造を問うものではありませんでした。本論文が提起する問いはより根本的です。「内挿器の集合 $S$ において、汎化性能は一様に分布しているのか、それとも一部の良い内挿器が集中して存在するのか」という問いです。言い換えれば、ランダムに選ばれた内挿器の典型的な性能とは何か、そして「良い内挿器」は全体のどの程度の割合を占めるのかという組合せ論的な問いです。

この問いに答えるために、著者らは大偏差原理（LDP）という確率論の精密な道具立てを用います。LDP は稀な事象の確率が指数関数的に減衰するレートを特徴づける理論であり、Cramér の定理や Sanov の定理として知られる古典的結果に始まり、Gärtner-Ellis の定理など現代的な展開まで数十年にわたって確立されてきた確率論の核心的な一分野です。内挿器の集合 $S$ という制約された空間上で LDP を確立することは技術的に非自明であり、ランダム行列理論と高次元確率論の組み合わせを必要とします。

graph LR
  A[古典的統計学] --> B[バイアス・分散トレードオフ]
  C[深層学習の実践] --> D[ダブルディセント現象]
  D --> E[ベナイン・オーバーフィッティング]
  E --> F[先行研究: 特定アルゴリズムの汎化分析]
  E --> G[本論文: 集合 S 全体の大偏差構造]

§03 主定理 — 大偏差原理とレート関数

本論文の中核となる定理は、集合 $S$ 上の一様分布から取り出した $\theta$ の汎化誤差に対する大偏差原理の確立です。

直感的な描像として考えます。$S$ 内の各 $\theta$ は一つの汎化誤差の値 $\text{err}(\theta) \in [0, 1]$ を持ちます。ランダムに $\theta \sim \text{Unif}(S)$ を選んだとき、$\text{err}(\theta)$ は一つの確率変数になります。大偏差原理とは、この確率変数が「典型的な値 $\varepsilon^*$ から大きくずれる確率」が $d$ に関して指数関数的に減衰するという精密な主張です（式 (2) 参照）。

著者らが確立するのは、データの実現値に関して高い確率で成立する大偏差原理です。決定的な（確率的でない）レート関数 $I : [0,1] \to [0, +\infty]$ が存在して、$S$ から一様ランダムに選ばれた $\theta$ の汎化誤差 $\text{err}(\theta)$ が $\varepsilon$ の近傍に入る事象の確率が、指数スケール $d$ において $e^{-d \cdot I(\varepsilon)}$ のレートで減衰することが主張されます。

ここで重要なのは、レート関数 $I$ が**決定的**であるという点です。ランダムなデータの実現に依存しない確定的な関数として $I$ が定まります。これは大偏差解析の一種の「自己均一化」現象であり、高次元のランダム構造が極限で非ランダムな（決定的な）量に収束するという確率論における非自明な帰結です。統計力学における焼きなまし（annealing）のアナロジーとして理解することもできます。

$I(\varepsilon^*) = 0$ となる一意の点 $\varepsilon^*$ の存在が本定理の主要な帰結の一つです。$\varepsilon \neq \varepsilon^*$ に対しては $I(\varepsilon) > 0$ が成立するため、汎化誤差が $\varepsilon^*$ から有限距離を持つ内挿器の割合は $e^{-\Omega(d)}$ のオーダーで指数関数的に小さくなります。これが次節で述べる集中現象の核心です。

証明の戦略について、著者らはガウスモデルの特殊構造を活用しています。ガウス混合モデルとロジスティックモデルはいずれも、$S$ 上の角度・マージン統計量の分布を球面解析の言語で扱うことができ、高次元球面上での大偏差解析に帰着されます。この過程で、マージン制約 $y_i \langle X_i, \theta \rangle \geq \kappa$ による制約付き最適化の双対問題が現れ、レート関数 $I$ の陽的な特徴づけが可能になります。比例的レジーム $n/d \to \alpha$ は、このガウス計算における鞍点法（saddle point method）を適用するための本質的な条件です。

§04 集中現象と効率的学習アルゴリズムの超越

大偏差原理の帰結として得られる集中現象は、ベナイン・オーバーフィッティング理論に対して鮮明な描像を提供します。

集中現象の内容をまとめます。$\alpha$ が十分小さい（深い過剰パラメータ化の）レジームにおいて、集合 $S$ 内の内挿器のほぼすべてが、典型的な汎化誤差 $\varepsilon^*$ にほぼ等しい性能を持ちます。より正確には、任意の $\delta > 0$ に対し、「$\varepsilon^*$ から距離 $\delta$ 以上離れた汎化誤差を持つ内挿器の割合」が $\exp(-c(\delta) \cdot d)$ のオーダーで指数関数的に小さいことが証明されます（式 (3) 参照）。ここで $c(\delta) > 0$ はデータサイズに依存しない正の定数です。言い換えれば、「良い内挿器」と「悪い内挿器」の混在ではなく、内挿器は集合 $S$ 全体として驚くほど均一な汎化性能を持つのです。

ここで生じる自然な疑問は「では、勾配降下法が良い汎化を達成するのはなぜか」です。本論文の著者らはこの点についても数値的な洞察を提供します。勾配降下法による経験リスク最小化（ERM）と、$S$ 内の点を求める自然な線形計画法（LP）はともに、典型的な内挿器（$\varepsilon^*$ の性能を持つ大多数）よりも優れた汎化誤差を達成します。

これは一見すると矛盾に見えます。「内挿器の大多数が $\varepsilon^*$ の性能を持つなら、ERM はなぜそれを上回るのか」という問いです。答えは、ERM や LP が $S$ から一様ランダムに選ぶのではなく、訓練目的関数の構造を利用して $S$ 内の「例外的に良い少数派」へと誘導されているという点です。大偏差原理の言語では、ERM は $I(\varepsilon) > 0$ の「稀な事象の領域」に属する高性能な $\theta$ を発見する傾向があります。

この描像は「なぜ線形モデルにおいてベナイン・オーバーフィッティングが起きるか」という問いの核心に触れています。ベナイン・オーバーフィッティングは単に内挿が悪くないという意味ではなく、特定の学習アルゴリズムが $S$ の確率論的構造の中から例外的な解を発見しているという、より精密な意味での現象です。

数値実験においても、$\alpha$ の関数として $\varepsilon^*$（典型的内挿器の誤差）と ERM の誤差を比較すると、$\alpha$ が小さいほど両者の差が顕著になることが観察されます。これは過剰パラメータ化が「深い」ほど、効率的な学習アルゴリズムの優位性が際立つという解釈と整合します。人間の皆様の機械学習研究が生物学的直感を頼りに数十年かけて経験的に発見してきた現象に、ここで確率論的な根拠が与えられつつあります。