Which Spaces can be Embedded in $L_p$-type Reproducing Kernel Banach Space? A Characterization via Metric Entropy

技術要約：「$\mathcal{L}_p$型再生核バナッハ空間に埋め込み可能な空間とは何か？ メトリックエントロピーによる特徴付け」

問題提起
本論文は、機械学習の理論的基礎における根本的な問い、すなわち、学習可能な関数クラスのモデリング・フレームワークとしての再生核バナッハ空間（RKBS）、特に$\mathcal{L}_p$型RKBSの範囲と限界を決定することを扱っている。RKBSは、複雑な推定器（ニューラルネットワークなど）を特徴付けるための柔軟なフレームワークを提供し、ヒルベルト空間と比較して（$\ell_p$ノルムによるスパース性などの）利点を持つ一方で、任意の効率的に学習可能な関数空間を埋め込むのに十分な汎用性を備えているかについては、依然として不明である。

既存の文献では、ある関数空間を再生核ヒルベルト空間（RKHS）に埋め込むことは、そのメトリックエントロピーの成長に対する特定の境界を意味することが確立されている。しかし、その逆、すなわちメトリックエントロピーの成長に関する境界が、特定の型のバナッハ空間への埋め込み可能性を意味するかどうかについては、一般的な$p$に対して完全には特徴付けられていない。著者らは以下の問いに取り組んでいる：多項式個のデータ点（過剰リスクに対して）で学習可能なあらゆる関数クラスは、$\mathcal{L}_p$型RKBSに埋め込むことができるのか？

手法
著者らは、メトリックエントロピーと関数空間の$\mathcal{L}_p$型RKBSへの埋め込み可能性との間の新しい接続を確立している。その手法は、以下の論理的ステップに従う：

1. メトリックエントロピーからラデマッハー複雑さへ： 著者らは、古典的な結果（マスアートの補題およびダドリーの連鎖定理）を抽象的なバナッハ空間へと一般化している。もしバナッハ空間$E$の単位球のメトリックエントロピーが（ターゲット空間$F = \ell_\infty(\Omega)$において）$\mathcal{E}_E^F(\delta) \leq \delta^{-p}$ ($p \geq 2$) のように多項式的に成長する場合、そのラデマッハー複雑さは$n^{-1/p}$の速度で減衰することを証明している。
2. ラデマッハー複雑さからバナッハ空間の型へ： 重要な技術的貢献は、ラデマッハーノルムの境界がバナッハ空間の**型（Type）**を意味することを示す新しい補題である。具体的には、ラデマッハー複雑さが$n^{-1/p'}$として減衰する場合、その空間（ターゲットノルムを装備したもの）は、任意の$s' < p'$に対して型$s'$を持つ。
3. 型から$\mathcal{L}_p$型埋め込みへ： 著者らは、定理3（ピッチの支配定理およびモーレイ・ピシエの定理の系）を活用し、確立された「型」の性質を利用して、仮説空間の同型な埋め込みを$\mathcal{L}_{s'}(\mu)$の閉部分空間へと構成する。
4. RKBSの構成： ハーン・バナッハの拡張定理および$\mathcal{L}_{s'}$と$\mathcal{L}_s$の双対性（$1/s + 1/s' = 1$）を用いて、特徴写像 $\Phi: \Omega \to \mathcal{L}_s(\mu)$ を構成する。この特徴写像は、元の空間$E$が$\mathcal{B}_s$に埋め込まれ、さらに$\mathcal{B}_s$が有界関数空間 $\ell_\infty(\Omega)$ に埋め込まれるような、$\mathcal{L}_s$型RKBSを誘導する。

主な貢献

• 逆の特性付け： 本論文は、古典的なRKHSの結果に対する逆を証明している。RKHSへの埋め込みはメトリックエントロピーの境界を意味するが、著者らは、メトリックエントロピーの成長に関する多項式的な境界（$\delta^{-p}$）が、ある$s > p$に対して$\mathcal{L}_s$型RKBSへの埋め込みを保証するのに十分であることを証明した。
• メトリックエントロピーによる統一的フレームワーク： 関数空間によって異なる特定の幾何学的性質（Type-2のチェックなど）に依存する従来のアプローチとは異なり、本研究はメトリックエントロピーに基づく統一的なアプローチを提供する。
• 学習可能性と幾何学の連結： 「多項式的な学習可能性」（誤差に対して多項式的に大きなデータセットでの学習）という概念を、$\mathcal{L}_p$型RKBSの幾何学的構造に直接結びつけている。任意の効率的に学習可能な関数クラスは、必要なメトリックエントロピーの境界を備えていることを示している。

主な結果

• 定理4： 有界な領域 $\Omega \subset \mathbb{R}^d$ と、$F = \ell_\infty(\Omega)$ にコンパクトに埋め込まれるRKBS $E$ が与えられたとき、メトリックエントロピーの成長が $\mathcal{E}_E^F(\delta) \leq \delta^{-p}$ ($p \geq 2$) で抑えられるならば、任意の $s > p$ に対して、$E \hookrightarrow \mathcal{B}_s \hookrightarrow F$ を満たす $\mathcal{L}_s$型RKBS $\mathcal{B}_s$ が存在する。
• 学習可能性への含意： 多項式的な学習可能性はメトリックエントロピーの多項式的境界を意味するため、この結果は、$\mathcal{L}_p$型RKBSが、あらゆる効率的に学習可能な関数クラスを表現できる強力かつ表現力豊かなモデルクラスであることを裏付けている。
• 技術的境界： 本論文は、エントロピー指数$p$と要求されるRKBSのパラメータ$s$の関係に関する明示的な境界を提供しており、$s$を$p$にいくらでも近く（具体的には $s > p$）選べることを示している。

意義と主張
著者らは、彼らの結果が、複雑な関数空間を学習するためのカーネル法の能力と限界に新たな光を当てるものであると主張している。$\mathcal{L}_p$型RKBSが、制御された（多項式的な）メトリックエントロピーを持つあらゆる関数クラスをモデル化するのに十分な汎用性を持っていることを示すことで、本論文は、これらの空間を広範な理論的フレームワークとして使用することを正当化している。

その意義は、特性付けの実行可能性にある。例えば、古典的なソボレフ空間やベゾフ空間において、明示的な埋め込みを見つけることよりも、メトリックエントロピーを推定することの方が実用的であることが多い。したがって、本研究は、特定の関数空間が$\mathcal{L}_p$型RKBSを用いて効果的にモデル化できるかどうかを判断するための、検証可能な条件を提供している。著者らは、このアプローチが、関数空間の性質、学習理論、および非ヒルベルト設定における埋め込みの研究を統合し、従来のType-2に基づいた特性付けよりも多才なフレームワークを提供することを強調している。