技术摘要：通过凯莱表补全分离几何压缩与算法压缩

1. 问题陈述

本文指出了统计学习理论（SLT）中几何压缩与算法压缩之间的根本理论分歧。

• 几何压缩： 现代深度学习依赖于连续容量控制机制（例如基于范数的正则化、间隔最大化、低秩偏差）。这些方法假设简洁的概念位于平滑流形或低维线性子空间上。虽然这种方法在处理连续数据时取得了成功，但该范式无法外推精确的算法或离散代数规则。
• 算法压缩： 经典学习理论（PAC 学习、奥卡姆剃刀、最小描述长度）将学习表述为恢复精确、最小逻辑规则的过程。然而，优化离散算法复杂度通常是 NP 难的，导致现代 SLT 在很大程度上放弃了它。
• 差距： 深度学习缺乏对算法复杂度最小化的归纳偏置。因此，神经网络在处理需要精确离散代数结构的任务时（例如算法任务上的长度泛化、发现精确对称性）往往力不从心，通常诉诸于脆弱的记忆而非规则抽象。

本文提出凯莱表补全作为解决这一缺失偏置的基准测试任务。该任务涉及从部分观测中恢复离散二元运算（群或拟群结构），作为矩阵补全的离散代数对应物。

2. 方法论与理论框架

基准任务：凯莱表补全

与寻求低线性秩（即行线性相关）的矩阵补全不同，群的凯莱表是拉丁方，其中各行互为排列。这种结构本质上排除了线性冗余。代数群的真正简洁性源于结合律公理，该公理约束全局结构以最小化结构描述长度。

算子值张量分解

为了在不进行不可处理的组合搜索的情况下解决此问题，本文利用了基于 Huh (2025) 近期工作的连续可微方法：

1. 张量表示： 有限集合 $Q$（大小为 $n$）上的二元运算 $\circ$ 由结构张量 $\delta \in \{0, 1\}^{n \times n \times n}$ 表示，其中若 $a \circ b = c$，则 $\delta_{abc} = 1$。
2. 分解模型： 该张量通过算子值分解进行建模：
   $$T_{abc}(\Theta) := \frac{1}{n} \text{Tr}(A_a B_b C_c)$$
   其中 $\Theta = (A, B, C)$，且 $A_a, B_b, C_c$ 是 $n \times n$ 矩阵切片（线性算子）。
3. 平坦性先验： 优化目标包含一个平坦性先验，用于惩罚经验重构损失的 Hessian 矩阵的迹：
   $$H(\Theta) := \text{Tr}\left(\nabla^2 \sum_{(a,b,c) \in \Omega} (T_{abc}(\Theta) - \delta_{abc})^2\right)$$

变分表征

目标函数 $H(\Theta)$ 分解为两个诱导离散性质的关键分量：

• 几何对齐（共线性）： 强制执行结合律公理。
• 逆 $\ell_2$ 惩罚： 在共线流形内充当精确的逆秩惩罚。

关键在于，该机制将参数推向满秩酉性，这与标准几何压缩的低秩偏差截然相反。

3. 主要结果与证明

本文基于所提出的框架提出了以下理论发现：

• 精确恢复界： 在完全观测极限下，几何下确界 $H_{\inf}(\delta) := \inf_{T(\Theta)=\delta} H(\Theta)$ 被证明是代数复杂度的精确、可微度量。
• 下界： 该目标确立了一个绝对下界 $H_{\inf}(\delta) \ge 3|\delta|$（其中 $|\delta| = n^2$）。
• 最小化器表征： 当且仅当目标运算同构于群时，该下界得以达到。在这种情况下，全局最小化器唯一地表征了底层群的正则表示（在酉规范意义下）。
• 概念验证： 这提供了形式化证明，表明基于连续梯度的优化可以原生地发现离散代数公理（特别是结合律），而无需诉诸组合搜索。

4. 提出的开放问题

本文挑战学界通过两个具体的开放问题来形式化几何压缩与算法压缩之间的分离：

1. 开放问题 1（形式化分离）： 建立几何容量控制（例如 Rademacher 复杂度、间隔界）与算法压缩之间的严格分离定理。目标是刻画假设类（例如离散代数规则），其中纯粹的几何泛化界被证明是空洞的（需要指数级样本复杂度），而可微算法复杂度度量则能提供紧密的多项式保证。
2. 开放问题 2（凯莱表补全的样本复杂度）： 形式化建立平坦性正则化张量分解的精确恢复保证。具体而言，能否证明在仅给定$O(n \log n)$个均匀采样条目的情况下，全局最小化器能以高概率完美补全群表？这将与标准矩阵补全理论形成对比，后者对于满秩结构产生的空洞界超过了 $O(n^2)$。

5. 意义与局限性

意义

本文认为，形式化并解决凯莱表补全问题将：

• 在经典逻辑驱动时代与现代几何驱动时代的 SLT 之间架起一座严谨的数学桥梁。
• 提供一个概念验证，表明精心设计的纯连续先验可以迫使梯度下降原生地优化精确的组合性质。
• 解决 SLT 中关于几何代理失效而算法压缩成功的关键缺失基础。

局限性与当前状态

• 部分结果： 本文承认，虽然存在性证明和景观分析已经存在（Huh, 2025），但关于精确理论边界的基础性问题仍然悬而未决。
• 神经符号局限性： 当前的神经符号方法受到批评，因为它们要么将逻辑松弛为近似概率（无法恢复刚性结构），要么依赖外部符号引擎来处理逻辑约束（无法实现原生的算法发现）。
• 范围： 本文侧重于建立理论框架并提出开放问题。它并不声称已在本文内解决了样本复杂度界（开放问题 2）或一般分离定理（开放问题 1），而是将它们定位为领域发展的必要下一步。