技術的概要：スケール感応的なシャッター：最適スケールにおける学習可能性と評価可能性

問題設定

本論文は、実数値関数クラスに関する統計的学習理論の根本的な問いに取り組む。具体的には、非学習的学習可能性、一様収束、およびVC 次元のスケール感応的な一般化であるファット・シャッター次元の 3 つの核心的概念間の厳密な関係を調査する。

「PAC 学習の基礎定理」は二値分類におけるこれらの概念の同等性を確立しているが、実数値設定では歴史的にギャップが存在していた。先行研究（例：Bartlett と Long, 1998）は、有限な $\gamma$-ファット・シャッター次元が一様収束と学習可能性を意味することを示したが、それは $2\gamma$（または $c>2$ に対して $c\gamma$）のスケールにおいてのみであった。これにより、スケールにおける乗数 2 の係数が避けられないものかどうかという疑問が残された。この疑問は、Anthony と Bartlett (1999) の教科書において Phil Long に帰せられる仮説であった。

さらに、本論文は、ファット・シャッター次元との関係におけるメトリックエントロピー（被覆数の対数）の振る舞いにも取り組む。先行研究（Alon ら, 1997; Rudelson と Vershynin, 2006）はメトリックエントロピーの上限を与えたが、最適スケールにおいてサンプルサイズ $n$ への依存性を $O(\log^2 n)$ から $O(\log n)$ に改善できるかどうか、およびこれらの上限におけるスケール係数を Tight にできるかどうかは未解決であった。

最後に、本論文はこれらの理論的洞察を、積分確率距離（IPM）を用いた生成モデルの評価可能性と推定可能性に応用する。二値テスト関数に対する最近の二項分類（Aiyer ら, 2026）は、そのような距離が推定可能か、あるいは最適スケール $c=3$ で弱く評価可能かのいずれかであることを示唆していた。これを実数値関数へ拡張することは、前述の一様収束結果におけるスケールギャップによって阻まれていた。

手法

著者らの主要な技術的革新は、パッキング数を経由する標準的な迂回路を避けた、経験的 $\ell_\infty$ 被覆数への直接的上限である。

1. 部分概念クラスによる直接被覆:
   被覆数をパッキング数に関連付けること（本質的にスケールの損失を伴う）の代わりに、著者らは部分概念クラスの理論（Lon01; AHHM22）を利用する。彼らは、スケール $\gamma$ に対する閾値に基づき、実数値関数を部分二値関数に写像する。これら誘導された部分クラスの VC 次元を上限付けることで、指数関数的でないサイズの明示的な被覆を構成する。これにより、$2\gamma$ ではなく、最適スケール $\gamma/2$ において直接被覆数上限を導出することが可能となる。

2. 反復的洗練:
   $\gamma/2$ に任意に近いスケールで上限を得るために、著者らは反復的構成を採用する。粗い被覆から始め、ボックスを再帰的に洗練し、半径を幾何学的に減少させながら被覆サイズの増大を制御する。これにより、$n$ に対して線形未満であるメトリックエントロピー $H(F, \gamma/2 + \epsilon, n)$ の上限が得られる。

3. サンプル圧縮と双対クラス:
   スケールが大きい領域（$\gamma > 2\gamma^*$）において、著者らはサンプル圧縮スキームを利用する。有限なファット・シャッター次元を持つ関数クラスの実対クラスもまた一様収束を満たすという事実（主要定理から導かれる結果）を活用し、分布を疎化して定数サイズの圧縮スキームを構築する。これにより $O(\log n)$ のエントロピー上限が導かれる。

4. 全変動距離への還元:
   評価可能性への応用において、著者らは無限のファット・シャッター次元を持つ一般的な IPM から、全変動（TV）距離設定への還元を構成する。シャッターされた集合上の分布の混合を慎重に構成することで、IPM が漸近的に TV 距離のように振る舞い、最適スケール定数を保持することを示す。

主要な貢献と結果

1. スケールギャップの解決（定理 1）

本論文は、実数値クラスに対する PAC 学習の基礎定理の厳密なアナログを確立する。有界な関数クラス $F$ とスケール $\gamma > 0$ に対して、以下の 3 つは同値である：

1. $F$ は $\gamma/2$-学習可能である。
2. $F$ は $\gamma$-一様収束を満たす。
3. 任意の $\gamma' > \gamma$ に対して、$F$ の $\gamma'$-ファット・シャッター次元は有限である。

意義: この結果は、係数 2 のギャップが避けられないという仮説を否定する。ファット・シャッター次元が $\gamma$ より厳密に大きい任意のスケールで有限であれば、学習可能性と一様収束はそれぞれ最適スケール $\gamma/2$（学習可能性について）および $\gamma$（収束について）で成り立つことを証明する。

2. 鋭いメトリックエントロピー上限（定理 2）

本論文は、臨界スケール $\gamma^* = \inf\{\gamma : \text{fat}_\gamma(F) < \infty\}$ に基づくメトリックエントロピー $H(F, \gamma, n)$ の増大を完全特徴づける：

• 線形領域（$\gamma < \gamma^*/2$）: $H(F, \gamma, n) = \Theta(n)$。
• 中間領域（$\gamma^*/2 < \gamma \le 2\gamma^*$）: $H(F, \gamma, n) = O(\log^2 n)$。本論文は、$\gamma \in (\gamma^*/2, \gamma^*)$ においてこの上限が（低次項を除き）tight であることを示し、Alon ら (1997) による $\log^2 n$ 係数の必要性に関する問いを解決する。
• 大スケール領域（$\gamma > 2\gamma^*$）: $H(F, \gamma, n) = O(\log n)$。これは、十分に大きなスケールにおいて指数を 1 に減少できることを確認し、Rudelson と Vershynin (2006) による問いを解決する。

3. 生成モデルの評価可能性に関する二項分類（定理 3 および命題 1）

鋭いスケール感応的結果を適用し、本論文は有界な積分確率距離（IPM）に対する二項分類を確立する：

• すべての $\gamma > 0$ に対してファット・シャッター次元が有限の場合、IPM は推定可能であり（したがって $c=1$ で強く評価可能）、
• いくつかの $\gamma \in (0, 1/2)$ に対してファット・シャッター次元が無限の場合、IPM は最適スケール $c=3$ で弱く評価可能であるが、$c < 3$ に対しては評価不可能である。

意義: これは、Aiyer ら (2026) による二値の二項分類を実数値関数へ拡張するものである。証明は、係数 2 の損失なしにスケール $\gamma$ において一様収束を確立する著者らの能力に決定的に依存している。これがなければ、最適スケール $c=3$ に関する議論は失敗する。

4. 閉包性

本論文は、$\gamma$-学習可能性と $\gamma$-一様収束の性質が以下の操作に対して不変であることを示す：

• 双対性: 一様収束するクラスの実対クラスもまた一様収束する。
• 集約: 1-リプシッツ関数によるクラスの集約は、同じスケールで一様収束を保持する。

意義と主張

著者らは、自らの研究が学習理論におけるいくつかの長年の未解決問題を解決すると主張する：

1. 係数 2 の仮説の否定: 学習可能性と一様収束が最適スケールで成り立つことを証明することで、Anthony と Bartlett (1999) が提起した問いに決定的な答えを与え、係数 2 のギャップが本質的ではないことを示す。
2. 鋭いエントロピー上限: メトリックエントロピーがサンプルサイズ $n$ とスケール $\gamma$ にどのように依存するかを確定し、$O(\log n)$ 上限が達成可能となる場合と $O(\log^2 n)$ が必要となる場合を明確にする。
3. 評価可能性の質的特徴づけ: 一様収束のスケールにおける係数 2 から 1 への量的改善が、生成モデル評価の質的特徴づけを解き放つと論じる。これにより、推定可能性と $c=3$ の弱評価可能性の間の鋭い二項分類が確立される。

著者らは、漸近的な振る舞いと二項分類の存在を解決したが、中間範囲 $\gamma^* < \gamma \le 2\gamma^*$ におけるエントロピーの正確な振る舞いと、最適スケールでの学習に関するシャープなサンプル複雑性上限は未解決問題のまま残っていると指摘する。さらに、他の $\ell_p$ メトリック下でのファット・シャッター次元と被覆数の関係は、将来の研究に委ねられている。