Approximating invariant functions with the sorting trick is theoretically justified

技术摘要：利用排序技巧近似不变函数

问题陈述
许多机器学习应用（包括集合预测、点云分类和图神经网络）都利用了群不变性。一种标准的方法是实施框架平均（frame averaging），即通过对一组群变换进行平均来使函数对称化。虽然群平均（group averaging）（对整个群进行平均）在理论上是鲁判的，但其计算成本非常高，特别是当群的基数很大时（例如置换群 $S_d$，其阶数为 $d!$）。

另一种替代方案是规范化（canonicalization），它将每个输入映射到唯一的轨道代表元（例如通过排序）后再进行评估。虽然规范化在计算上非常高效，但它往往会在生成的函数中引入不可微性或不连续性。因此，与群平均相比，规范化（特别是“排序技巧”）在近似理论中的理论性能保证在很大程度上仍未得到充分探索。本文旨在填补这一空白，为在再生核希尔伯特空间（RKHS）中使用规范化（特别是“排序技巧”）提供理论依据，尽管该方法在解析性质上表现较差（缺乏光滑性）。

方法论
作者专注于置换群 $S_d$ 作用于定义域 $X = [0, 1]^d$（通过坐标置换）的情况。他们比较了两种用于近似 $G$-不变函数 $f$ 的基于核的插值方法：

1. 标准群平均核 ($K_{perm}$)：通过对群进行对称化来定义。
2. 规范化（排序）核 ($K_{sort}$)：定义为 $K_{sort}(x, y) = K(\text{sort}(x), \text{sort}(y))$，其中 $\text{sort}(x)$ 将 $x$ 的坐标按降序重新排列。

本文构建了与 $K_{sort}$ 相关的 RKHS $\mathcal{H}_{sort}$，并分析了最小范数插值误差。其理论框架依赖于近似理论中的工具：

• 填充距离（Fill Distance, $h_{X,X}$）：衡量样本点在定义域内密度的度量。
• 内部锥条件（Interior Cone Conditions）：局部多项式重构所需的几何约束。作者指出，排序元素的基本域（fundamental domain, $X_{sort}$）在边界附近存在“狭窄角落”，这会降低这些条件。
• 重排原理（Rearrangement Principle）：这是一个数学洞察，即对于排序向量 $w$ 和 $z$，其点积 $w \cdot z$ 与任何其他置换相比都是最大的。这意味着排序后的评估点在核度量下在几何上比未排序的数据点更“接近”。

核心贡献与结果

1. 近似误差界限：

   • 逐点误差：作者推导了逐点近似误差的上界。他们表明，虽然通过排序可以改善误差界限，但由于 $K_{sort}$ 缺乏可微性，该界限在基本域的边界（即坐标相等处）附近会变弱。
   • $L_2(P)$ 误差：至关重要的是，作者证明了随着样本点数量 $n$ 的增加，误差较大的“边界区域”的测度趋于零。因此，排序核的全局 $L_2(P)$ 近似误差严格优于未排序的核。
   • 填充距离缩减：利用重排原理，他们证明了对于任何设计序列，排序后点的填充距离小于或等于未排序点的填充距离（$h_{sort X, sort X} \leq h_{X, X}$）。此外，他们展示了存在一种设计序列，使得填充距离可以减少 $(d!)^{1/d}$ 倍。

2. 特征值衰减率：

   • 本文分析了与核相关的积分算子的特征值衰减率。对于 $C^\nu$-光滑核，特征值通常以 $O(j^{-\nu/d})$ 的速率衰减。
   • 作者表明，排序核的特征值衰减率比未排序核快一个 $(d!)^{\nu/d - 1}$ 的因子（前提是 $\nu/d > 1$）。这表明排序核定义了一个“更小”或受限程度更高的函数空间，从而促进了更快的收敛。

3. 空间嵌入：

   • 理论结果确立了嵌入关系 $\mathcal{H}_{perm} \subset \mathcal{H}_{sort}$（在 $L_2(X, P)$ 中）。这意味着排序后的 RKHS 能够重现原始 RKHS 中任何置换不变子空间中的函数，从而证明了用排序核替换计算昂贵的群平均核的合理性。

4. 数值验证：

   • 在维度 $d \in \{3, 6, 9, 12\}$ 下对正弦叠加函数（sum of sinusoids）进行的实验证实了上述理论发现。排序核（包括高斯核和神经网络核）始终优于其对应的未排序核，且随着维度 $d$ 的增加，这种性能差距不断扩大。

意义与主张
本文声称，尽管规范化（排序）方法具有已知的不可微性，但它为规范化在不变学习中的经验成功提供了首个严谨的理论证明。作者认为，排序的高效性不仅仅是一个启发式的权衡，而是得到了理论支持，具体体现在：

• 减少了填充距离，而填充距离是插值误差界限中的关键因素。
• 特征值衰减更快，意味着更高效的不变函数表示。
• 基本域边界处的“病态”不可微性对全局 $L_2$ 误差的影响随着样本密度的增加而变得微不足道。

这项工作表明，“排序技巧”有效地利用了基本域的几何特性来提高近似速率。作者总结道，虽然如何选择能充分利用该技术的设计序列仍是一个开放的研究课题，但理论界限确认了规范化是处理高维不变近似时，一种可行且优于群平均的替代方案。