技术摘要：在线算法无法找到孤立的感知器解

1. 问题陈述

本文研究了二值感知器问题（binary perceptron problem），这是一个随机约束满足问题（CSP），其目标是寻找一个符号向量 $\sigma \in \{\pm 1\}^n$，使得在给定具有 i.i.d. 标准高斯条目的 $m \times n$ 矩阵 $G$ 的情况下，$G\sigma \ge \kappa\sqrt{n}$ 逐分量成立。研究是在比例机制下进行的，即对于固定的约束密度 $\alpha > 0$，令 $m = \lfloor \alpha n \rfloor$。

该模型的一个定义特征是强冻结性（strong freezing）：对于任何 $\alpha > 0$，几乎所有的解都是孤立的。具体而言，以高概率而言，每一个解与其他任何解之间的汉明距离均为 $\Omega(n)$。这种几何特性表明，高效算法可能会难以找到解，因为不存在“临近”的解来引导局部搜索。

然而，这里存在一个悖论：高效算法，特别是在线算法（它们逐个处理 $G$ 的列并不可逆地分配符号），已知能在某些约束密度下（例如当 $\kappa=0$ 时，$\alpha < 0.327$）找到解。核心问题在于：这些成功的在线算法找到的是典型的孤立解，还是定位到了稀有的、连接良好的解簇？

2. 方法论与证明策略

作者证明了在线算法无法以任何常数概率找到孤立解；其成功概率随 $n \to \infty$ 而趋于零。证明过程分为三个主要技术阶段：

A. 归约为确定性算法

作者首先观察到，任何随机在线算法都可以通过平均化论证进行分析。只需考虑确定性在线算法，其中在第 $t$ 步的符号 $\sigma_t$ 是当前列 $g_t$、列的历史以及先前分配的符号的可测函数。

B. “停止学习”引理（后缀并行基准）

核心洞察是，如果一个在线算法成功输出了一个 $h$-孤立解（其中 $h = \omega(\log^4 n)$），那么它必须在过程接近尾声时有效地“停止学习”。

• 逻辑： 如果一个算法输出的是一个孤立解，那么最后的 $r$ 个符号（其中 $r < h$）必须由解的前缀唯一确定。如果算法仍在“学习”（即根据剩余列的具体顺序改变其决策规则），它就有可能输出一个非唯一的补全，从而违反孤立性质。
• 构造： 作者定义了一个**后缀并行基准（suffix-parallel baseline）**算法，记作 $\text{Alg}^{(r)}$。该算法在处理前 $n-r$ 列时与原算法 $\text{Alg}$ 行为一致。然而，对于最后的 $r$ 列，它将这些列视为在步骤 $n-r+1$ 时同时到达。具体来说，它对每一个后缀列 $Y_i$ 应用相同的决策函数 $\phi = \text{SubAlg}_{n-r+1}$，忽略了在后缀内的特定到达顺序。
• 结果： 利用高斯列的可交换性以及平均化论证，他们表明对于任何成功的算法，存在一个 $r$，使得该算法的输出以高概率与此后缀并行基准一致。

C. 基准的反集中性

证明的第二部分证明了没有任何后缀并行基准能够产生唯一的补全。

• 设置： 设基准使用固定函数 $\phi$ 为后缀列 $Y_1, \dots, Y_r$ 分配符号 $z_i$。满足该线性约束的条件是和 $\frac{1}{\sqrt{r}}\sum z_i Y_i$ 必须位于特定的区域内（一个经过前缀约束偏移的上正交锥）。
• 唯一性约束： 为了使解是孤立的，字符串 $z$ 必须是满足该线性约束的 $\{\pm 1\}^r$ 中的唯一字符串。
• 几何论证： 这种唯一性意味着随机向量 $S_\phi = \frac{1}{\sqrt{r}}\sum \phi(Y_i)Y_i$ 必须落在 $\mathbb{R}^m$ 中的一个非常窄的“壳层”（两个上正交锥之间的差异）内。
• 概率界限： 作者应用 Berry-Esseen 定理 来用高斯随机变量 $Z$ 近似 $S_\phi$ 的分布。随后，他们调用了 Nazarov 不等式，该不等式提供了高斯向量的反集中界限。该不等式表明，高斯向量落在如此狭窄的壳层内的概率极小（$o(1)$）。
• 结论： 由于基准以 $o(1)$ 的概率产生唯一解，且任何成功的在线算法都必须本质上匹配这样一个基准，因此在线算法成功的概率为 $o(1)$。

3. 主要贡献与结果

主定理

定理 1.1（非正式）： 在每个约束密度 $\alpha > 0$ 和边际 $\kappa$ 下，每个在线算法找到二值感知器孤立解的概率均为 $o(1)$。

• 该结果适用于标准的二值感知器，并扩展到了对称二值感知器以及其他具有分离约束集的通用感知器模型。
• 孤立阈值被放宽至 $h = \omega(\log^4 n)$，这比文献中通常讨论的线性孤立（$\Omega(n)$）要弱得多，使得该结果具有鲁棒性。

与前人工作的比较

• Gong, Huang, Li, and Sellke [GHLS26]： 此前曾证明了稳定算法（其输出在输入重采样下仅发生微小变化的算法）找到孤立解的概率至多约为 $\approx 0.84$。
  • [GHLS26] 的局限性： 该界限是一个常数，而非趋于零。它并未排除成功概率为 $0.8$ 的算法。此外，尚不清楚目前已知的最佳在线算法（例如 Jo and Lee [JL26a]）是否在他们的意义上是稳定的。
• 本研究： 提供了一个针对在线算法的趋于零的界限（$o(1)$）。这明确排除了在线算法通过以任何常数概率找到孤立解而获得成功的可能性。

4. 意义与主张

本文解决了二值感知器问题中“统计-计算间隙（statistical-to-computational gap）”的关键环节。

• 解决悖论： 表面上的矛盾——即尽管解空间由孤立点主导，但高效的在线算法仍能找到解——通过证实 [BIL+15, BDVLZ20] 中提出的假设得到了解决。作者证明了在线算法无法找到典型的孤立解。因此，如果它们成功了，则必然是定位到了解空间中存在的指数级稀有的、连接良好的解簇。
• 算法硬度： 本工作建立了一种不同于**重叠间隙性质（Overlap Gap Property, OGP）**框架的新型在线算法硬度结果。虽然 OGP 是证明针对稳定算法之硬度的标准工具，但作者的证明依赖于在线设置的结构性约束（不可逆决策）和反集中性质，而非解之间重叠的几何性质。
• 适用范围： 该结果适用于广泛用于差异最小化和感知器学习的算法类别，包括 Jo 和 Lee [JL26a] 的最先进在线算法。它证实了这些算法在本质上无法在“冻结”的孤立解景观中进行导航。

总而言之，本文提供了严格的证明，表明在线算法在二值感知器问题中的成功，取决于是否存在且可触达稀有的非孤立解簇，而非其具备找到占主导地位的孤立解的能力。