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 提供了刻画复杂估计器（如神经网络）的灵活框架，并具有优于希尔伯特空间（Hilbert spaces）的优势（例如通过 $\ell_p$ 范数实现稀疏性），但目前尚不清楚 $\mathcal{L}_p$ 型 RKBS 是否足够通用，能够嵌入任意高效可学习的函数空间。

现有文献表明，将一个函数空间嵌入到再生核希尔伯特空间（RKHS）意味着其度量熵（metric entropy）的增长存在特定的界限。然而，关于逆命题——即度量熵增长的界限是否能蕴含对特定类型巴拿赫空间的嵌入性——对于一般的 $p$ 值尚未得到充分刻画。作者试图回答：每一个在多项式数量数据点（相对于超额风险）下可学习的函数类，是否都能被嵌入到一个 $\mathcal{L}_p$ 型 RKBS 中？

方法论
作者建立了度量熵与 $\mathcal{L}_p$ 型 RKBS 嵌入性之间的全新联系。其方法论通过以下逻辑步骤进行：

1. 从度量熵到 Rademacher 复杂度： 作者将经典的 Massart 引理和 Dudley 链式法则（Dudley's Chaining Theorem）推广到抽象巴拿赫空间。他们证明了，如果巴拿赫空间 $E$ 的单位球在目标空间 $F = \ell_\infty(\Omega)$ 中的度量熵满足 $\mathcal{E}_E^F(\delta) \leq \delta^{-p}$（其中 $p \geq 2$），那么该空间的 Rademacher 复杂度以 $n^{-1/p}$ 的速率衰减。
2. 从 Rademacher 复杂度到巴拿赫空间类型（Type）： 一个关键的技术贡献是提出了一个新的引理，证明了 Rademacher 范数的界限可以推导出巴拿赫空间的 Type。具体而言，如果 Rademacher 复杂度以 $n^{-1/p'}$ 的速率衰减，则该空间（配备目标范数）对于任何 $s' < p'$ 都是 $s'$ 型（Type $s'$）的。
3. 从 Type 到 $\mathcal{L}_p$ 型嵌入： 利用 定理 3（Pietsch 支配定理和 Maurey-Pisier 定理的一个推论），作者利用已建立的 Type 性质来构造一个同构嵌入，将假设空间嵌入到 $\mathcal{L}_{s'}(\mu)$ 的闭子空间中。
4. 构建 RKBS： 利用 Hahn-Banach 延拓定理以及 $\mathcal{L}_{s'}$ 与 $\mathcal{L}_s$ 的对偶性（其中 $1/s + 1/s' = 1$），他们构造了一个特征映射 $\Phi: \Omega \to \mathcal{L}_s(\mu)$。该特征映射诱导了一个 $\mathcal{L}_s$ 型 RKBS $\mathcal{B}_s$，使得原空间 $E$ 嵌入到 $\mathcal{B}_s$ 中，进而嵌入到有界函数空间 $\ell_\infty(\Omega)$ 中。

核心贡献

• 逆向刻画： 本文证明了经典 RKHS 结果的逆命题。虽然嵌入到 RKHS 意味着度量熵存在界限，但作者证明了多项式级的度量熵增长界限（$\delta^{-p}$）足以保证嵌入到某个 $\mathcal{L}_s$ 型 RKBS 中（其中 $s > p$）。
• 通过度量熵建立统一框架： 不同于以往依赖于随不同函数空间变化的特定几何性质（如 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$，存在一个 $\mathcal{L}_s$ 型 RKBS $\mathcal{B}_s$ 使得 $E \hookrightarrow \mathcal{B}_s \hookrightarrow F$。
• 对可学习性的意义： 由于多项式可学习性意味着多项式级的度量熵界限，该结果证实了 $\mathcal{L}_p$ 型 RKBSs 是一个强大且具有表现力的模型类，能够表示任何高效可学习的函数类。
• 技术界限： 论文提供了关于熵指数 $p$ 与所需 RKBS 参数 $s$ 之间关系的显式界限，表明 $s$ 可以被选择为任意接近 $p$（具体为 $s > p$）。

意义与主张
作者声称，其研究结果为理解核方法建模复杂函数空间的能力及其局限性提供了新的视角。通过证明 $\mathcal{L}_p$ 型 RKBSs 足以作为任何具有受控（多项式）度量熵的函数类的模型，本文验证了这些空间作为广泛理论框架的使用价值。

其重要性在于该刻画的实用性：在实践中（例如对于经典的 Sobolev 和 Besov 空间），估计度量熵通常比寻找显式的嵌入路径更为直接。因此，这项工作提供了一个可验证的条件，用于判断特定的函数空间是否可以有效地使用 $\mathcal{L}_p$ 型 RKBSs 进行建模。作者强调，这种方法统一了函数空间性质、学习理论以及非希尔伯特设置下的嵌入研究，提供了比以往基于 Type-2 特征的研究更具通用性的框架。