技术摘要：实现近似对称性比实现精确对称性在计算上容易指数倍

问题陈述

本文探讨了几何机器学习中的一个基本问题：强制实现精确对称性与近似对称性的计算成本有何差异？ 虽然精确对称性（不变性或等变性）是一种强大的归纳偏置，能够改善样本复杂度和泛化能力，但它往往施加了刚性约束，而这些约束在现实世界数据（如医学成像或对称性发现）中可能并不成立。相反，近似对称性提供了灵活性，但缺乏关于其相对于精确强制实现的效率方面的严格理论理解。

作者通过**平均复杂度（averaging complexity）的视角形式化了这一比较。他们考虑了一种设定，其中学习者可以访问一个黑盒模型，并且只能通过有限次数的动作查询（Action Queries, AQs）**对其进行后处理。一个 AQ 包括对变换后的输入 $gx$进行模型查询，其中$g$ 为群元素。目标是构建这些查询的线性组合（一种平均方案），使其产生的函数满足所需的对称性属性。“成本”被定义为该线性组合中所需的非零权重（查询）的最小数量。

方法论与框架

1. 平均复杂度定义

作者引入平均复杂度作为量化强制实现对称性难度的指标。

• 精确对称性： 若对于所有 $g \in G$ 都有 $f(gx) = f(x)$，则函数$f$具有精确对称性。复杂度$AC_{ex}(F)$是平均方案$\omega$的最小规模，使得生成的算子$E_\omega$将任意$f \in F$ 映射为精确对称函数。
• 近似对称性： 通过 $L^2(X)$-范数松弛来定义。
  • 弱近似对称性： 对随机 $g$ 而言，到对称性的期望 $L^2$ 距离被因子 $\epsilon$ 降低。
  • 强近似对称性： 对每一个 $g \in G$，到对称性的 $L^2$ 距离都被 $\epsilon$ 降低。
  • 复杂度 $AC_{wk}(F, \epsilon)$ 和 $AC_{st}(F, \epsilon)$ 衡量实现这些松弛所需的最小方案规模。

2. 理论工具

分析主要依赖于表示论和有限群上的傅里叶分析：

• 群表示： 群 $G$ 在函数空间 $F$ 上的作用被视为线性表示 $\rho$。
• 张量幂： 为了证明精确对称性的下界，作者分析了对称张量幂 $\text{Sym}^{\otimes k}(F)$。他们利用了一个事实，即随着 $k$ 的增加，张量幂最终会包含该群的所有不可约表示（irreps）。
• 群上的傅里叶变换： 平均方案 $\omega$ 被视为群上的信号。其傅里叶变换 $\hat{\omega}(\pi)$（其中 $\pi$ 为不可约表示）决定了平均算子的行为。
  • 对于精确对称性，$\hat{\omega}(\pi)$ 必须对所有非平凡不可约表示为零。
  • 对于近似对称性，$\hat{\omega}(\pi)$ 对非平凡不可约表示必须具有小的算子范数。

3. 证明策略

• 下界（精确对称性）： 作者表明，如果函数类包含足够高阶的张量幂（具体到 $K$ 阶），则平均方案必须在所有群元素上具有非零权重，以消除所有非平凡不可约表示。这迫使该方案必须是 $G$ 上的均匀分布，从而需要 $|G|$ 次查询。
• 上界（近似对称性）： 利用概率构造，作者证明大小为 $O(\log |G|)$ 的随机群元素子集足以以高概率使非平凡不可约表示的傅里叶系数变小（有界于 $\epsilon$）。这依赖于矩阵集中不等式（例如矩阵 Bernstein 不等式）。

主要结果

本文确立了精确对称性与近似对称性强制实现复杂度之间的指数级分离：

1. 精确对称性的线性复杂度：
   在“忠实群作用”假设下，存在一个依赖于群结构和函数类的阶数 $K$，使得在 $K$ 次多项式特征空间上强制实现精确对称性需要线性平均复杂度：
   $$AC_{ex}(\text{Sym}^{\otimes K}(F)) = |G|$$
   这意味着，为了保证丰富函数类的精确不变性，必须查询整个群。

2. 近似对称性的对数复杂度：
   对于任意函数类 $F$ 和任意精度 $\epsilon > 0$，弱近似对称性和强近似对称性的平均复杂度在群规模上均为对数级：
   $$AC_{wk}(F, \epsilon) = O\left(\frac{\log |G|}{\epsilon}\right), \quad AC_{st}(F, \epsilon) = O\left(\frac{\log |G|}{\epsilon}\right)$$
   该界限是普适的，不依赖于函数类的具体结构，仅取决于群规模。

3. 紧性：
   本文提供了下界证明，表明在某些情况下（例如当群是 $\mathbb{F}_2$ 上的向量空间时），近似对称性需要 $\Omega(\log |G|)$ 次查询，从而证实了对数上界在常数范围内是紧的。

实验验证

作者展示了一项涉及符号翻转对称性（$G = \{\pm 1\}^d$）回归任务的原理验证实验。

• 设置： 在一个由符号翻转不变的目标函数标记的数据集上训练神经网络。在评估时，对随机子集 $S \subset G$ 上的预测进行平均。
• 观察： 测试损失随着子集大小 $|S|$ 的增加而降低。关键在于，当 $|S| \approx 32$ 时（对于 $d=20$，即 $\log_2(2^{20})$），大部分性能提升已经实现，更大的子集带来的收益递减。
• 结论： 这从经验上验证了理论主张，即对数规模的子集能够捕捉到全群平均带来的益处。

意义与主张

本文声称在机器学习背景下提供了精确对称性与近似对称性之间的首个理论分离。其主要贡献包括：

1. 近似对称性的理论依据： 结果正式证明了为什么近似对称性在实践中往往更受青睐。它不仅仅是处理噪声的启发式方法；在查询复杂度方面，实现它的效率要高出指数级。
2. 新指标（平均复杂度）： 引入平均复杂度提供了一个量化对称性强制实现成本的新框架，独立于具体的模型架构。
3. 可推广性： 所开发的工具（平均方案的表示论分析）被提出具有独立的兴趣，可用于几何机器学习的更广泛研究，包括数据增强和对称性发现。

作者在范围上保持谦逊，指出结果适用于有限群，并将这些界限扩展到无限群或其他度量（$L^2$ 之外）仍然是一个未解决的挑战。他们强调，虽然精确对称性在理论上是“完美”的，但其指数级成本使得近似对称性成为大规模群在实际应用中的更优选择。