球面上平方和松弛的 Argmax 原理

An Argmax Principle for Sum-of-Squares Relaxations on the Sphere

arXiv: 2608.02594v1

论文信息

标题: An Argmax Principle for Sum-of-Squares Relaxations on the Sphere

作者: Fernando Jeronimo Granha, Pei Wu, Haochen Xu

发布日期: 2026-08-03

arXiv ID: 2608.02594v1

PDF 链接: 下载 PDF

3 分钟速览

  • 研究问题：该论文研究球面上多项式优化问题的平方和（SoS）松弛，为目标函数提供可计算的近似解，并分析收敛速度。

  • 核心方法：从可行伪期望中构建高次矩多项式（如 Φk(u)=E~⟨x,u⟩2k\Phi_k(u) = \widetilde{\mathbb{E}}\langle x,u\rangle^{2k}），以该多项式的极大值点作为舍入对象，利用其一阶和二阶最优性条件推导收敛界。

  • 关键结果：对最佳可分离态（BSS）问题，度-O(n/ε)O(\sqrt{n/\varepsilon}) 的 SoS 松弛可在完美完备性下判定 (1,1−ε)(1,1-\varepsilon)-BSS 间隙问题，参数依赖达到指数时间假设下的本质紧界（见第 3.6 节）。

  • 主要局限：该方法目前仅适用于球面约束下的优化问题，且对非球面扩展、一般约束的处理尚未讨论。

  • 适合读者：从事理论计算机科学、量子信息、优化理论研究的学者，希望理解 SoS 松弛收敛分析与舍入算法的读者。

论文背景和研究动机

球面上的多项式优化是现代算法复杂性理论中的基础连续优化问题之一。从谱方法中的二次型最大化到高阶张量范数估计，该框架涵盖了许多核心问题。当目标函数的次数超过二次时，问题变得本质困难，而平方和（Sum-of-Squares, SoS）松弛是处理此类问题的标准半定规划层级方法。

在度 2k2k 时，SoS 松弛使用"伪期望"E~\widetilde{\mathbb{E}}（行为类似于球面上分布的矩）在满足球约束的伪分布上优化目标函数。该框架在理论计算机科学和量子信息领域发挥着关键作用，尤其是在分析近似算法和复杂性下界时。

传统的 SoS 收敛分析存在两类技术路径：理论计算机科学往往将分析耦合到高效舍入算法（通过迭代重权、条件化到达低阶矩，再应用高斯舍入等过程），而优化和量子信息文献则通常采用调和分析、逼近理论和 de Finetti 型界。本文旨在探索一种更统一、初等的机制来统一这些看似不同的技术。

论文选择三个具有代表性的问题作为研究重点：最佳可分离态问题（BSS，量子信息中 QMA(2)\mathsf{QMA}(2) 验证的核心）、矩阵 2→42\to4 范数（与超收缩性、小集合扩张、Unique Games 猜想密切相关）、以及一般固定次数的球面多项式优化。这些问题的 SoS 分析之前分别依赖不同技术，本文则给出统一视角。

核心方法和技术细节

本文的 argmax 原理可以概括为：从可行伪期望构建的高次矩多项式之极大值点，是理解 SoS 收敛性的舍入对象。

2.1 方向性舍入：BSS 与矩阵范数

考虑 BSS 问题的对称版本：给定正交投影 PP，求 hsep(P)=max⁡x∈Sn−1⟨x⊗x,P(x⊗x)⟩h_{\mathsf{sep}}(P) = \max_{x\in\mathbb{S}^{n-1}}\langle x\otimes x, P(x\otimes x) \rangle。在 SoS 松弛中，我们有一可行伪期望 E~\widetilde{\mathbb{E}}，满足 ∥x∥22=1\|x\|_2^2=1 且 P(x⊗x)=x⊗xP(x\otimes x)=x\otimes x。定义方向矩多项式：

Φk(v)=E~⟨x,v⟩2k,v∈Sn−1\Phi_k(v) = \widetilde{\mathbb{E}}\langle x,v\rangle^{2k},\quad v\in\mathbb{S}^{n-1}

取 u=arg⁡max⁡Φku = \arg\max \Phi_k。重权 E~w\widetilde{\mathbb{E}}_w 定义为 E~w[f]=E~[s2k−2f]/E~[s2k−2]\widetilde{\mathbb{E}}_w[f] = \widetilde{\mathbb{E}}[s^{2k-2}f]/\widetilde{\mathbb{E}}[s^{2k-2}]，其中 s=⟨x,u⟩s=\langle x,u\rangle。

一阶导数条件表明 uu 是重权伪协方差矩阵 Σw=E~w[xx⊤]\Sigma_w = \widetilde{\mathbb{E}}_w[xx^\top] 的特征向量。二阶导数条件则控制谱间隙：对任意 h⊥uh\perp u、∥h∥2=1\|h\|_2=1，有

E~w[⟨x,h⟩2]≲E~w[⟨x,u⟩2]k\widetilde{\mathbb{E}}_w[\langle x,h\rangle^2] \lesssim \frac{\widetilde{\mathbb{E}}_w[\langle x,u\rangle^2]}{k}

由此推知，除最大特征值外，Σw\Sigma_w 的所有其他特征值贡献的 Frobenius 质量不超过 (n−1)/k2(n-1)/k^2 比例。当 k≳n/εk \gtrsim \sqrt{n/\varepsilon} 时，得到 ⟨u⊗u,P(u⊗u)⟩≥1−ε\langle u\otimes u, P(u\otimes u)\rangle \geq 1-\varepsilon，即可判定间隙问题。该分析比 Barak–Kothari–Steurer 的迭代进度算法更简洁，且将度依赖从 O~(n/ε2)\tilde{O}(\sqrt{n}/\varepsilon^2) 改进为 O(n/ε)O(\sqrt{n/\varepsilon})（见定理 1.1）。

对 2→42\to4 范数，argmax 原理的应用更进一步。设 τ\tau 为阈值且 E~[∥x∥44]≥τ\widetilde{\mathbb{E}}[\|x\|_4^4] \geq \tau。再次取 Φk(v)=E~⟨x,v⟩2k\Phi_k(v) = \widetilde{\mathbb{E}}\langle x,v\rangle^{2k} 的极大值点 uu，重权 w(x)=⟨x,u⟩2k−4w(x)=\langle x,u\rangle^{2k-4}。此时需要全局极大性（而非仅一阶、二阶最优性）来导出四阶矩集中不等式：对任意 h∈W∩u⊥h\in W\cap u^\perp，

E~w[⟨x,h⟩4]≲E~w[⟨x,u⟩4]k2\widetilde{\mathbb{E}}_w[\langle x,h\rangle^4] \lesssim \frac{\widetilde{\mathbb{E}}_w[\langle x,u\rangle^4]}{k^2}

将 xx 分解为 su+zsu+z（z=(P−uu⊤)xz = (P-uu^\top)x），并利用坐标型 SoS 不等式对 xi=sui+zix_i = s u_i + z_i 进行解耦，可得 E~w[∥z∥44]\widetilde{\mathbb{E}}_w[\|z\|_4^4] 被控制以约 E~w[⟨x,u⟩4]⋅nτ/k2\widetilde{\mathbb{E}}_w[\langle x,u\rangle^4]\cdot n\tau/k^2。因此 k∼n/εk \sim \sqrt{n}/\varepsilon 时，∥u∥44≥(1−ε)τ\|u\|_4^4 \geq (1-\varepsilon)\tau，实现对 2→42\to4 范数的 (1+ε)(1+\varepsilon)-乘法近似。该结果强化了 Barak 等的 exp⁡(Oδ(n))\exp(O_\delta(\sqrt{n})) 时间判定算法，首次在相同的次指数时间下给出了乘法近似比保证（见定理 1.2）。

2.2 折叠选择：一般多项式优化

对于度-dd 齐次多项式 f(x)f(x)，argmax 原理提升到"折叠"选择。设 TT 为 dd-线性形式且 f(x)=T(x,…,x)f(x)=T(x,\ldots,x)。定义折叠多项式：

Φk(u,v)=E~[T(u,v,x,x)2k]\Phi_k(u,v) = \widetilde{\mathbb{E}}[T(u,v,x,x)^{2k}]

其中 u,vu,v 为球面参数。若 (u∗,v∗)(u^*,v^*) 是 Φk\Phi_k 的极大值点，利用伪 Hölder 不等式和球面矩恒等式，可得：

max⁡x∈Sn−1T(u∗,v∗,x,x)2k≥Φk(u∗,v∗)≥cn,k2τ2k\max_{x\in\mathbb{S}^{n-1}} T(u^*,v^*,x,x)^{2k} \geq \Phi_k(u^*,v^*) \geq c_{n,k}^2 \tau^{2k}

其中 cn,kc_{n,k} 是 2k2k 阶球面矩，尺度约为 (k/n)k(k/n)^k，τ\tau 是伪期望下的目标值。这恢复了 Bhattiprolu 等的 Od((n/k)d/2−1)O_d((n/k)^{d/2-1}) 收敛界，但证明大为简化，无需其引入的弱解耦技术（见定理 1.4）。

创新点和贡献

  1. 统一的 argmax 原理：将高次矩多项式的极大值点作为通用分析对象，连接了谱间隙论证、高阶赝集中估计和折叠选择三种舍入机制。这种统一性使三个看似不同问题的分析归于同一框架。

  2. 改进 BSS 参数：对完美完备性 BSS，将 SoS 度依赖从 O~(n/ε2)\tilde{O}(\sqrt{n}/\varepsilon^2) 提高到 O(n/ε)O(\sqrt{n}/\varepsilon)，并在 ε=Θ~(1/n)\varepsilon=\tilde{\Theta}(1/n) 的逆线性间隙下匹配 ETH 下界，证明了算法的条件紧性（见第 3.6 节）。

  3. 乘法近似保证：对 2→42\to4 范数，首次在 exp⁡(O~(n))\exp(\tilde{O}(\sqrt{n})) 时间内获得 (1+ε)(1+\varepsilon)-乘法近似比，且推广到矩阵 p→qp\to q 范数（见定理 1.3）。

  4. 初等证明：对一般多项式优化，用简洁的伪 Hölder 和球面矩运算恢复原本需要精细弱解耦技术的结论（见第 6 节）。

局限与待解决问题

  1. 舍入算法的计算成本：尽管分析表明 uu 的一阶、二阶局部最优性即可驱动舍入，且可通过 Riemannian 信赖域方法找到近似二阶局部极大值点（见附录 A），但在实际计算中，高次多项式的优化仍可能需要较高的计算成本。论文提出的迭代搜索算法（第 4.6 节）依赖于对坐标圆进行离散搜索，当维度 nn 较大时搜索量可能可观。

  2. 球面限制：现有 argmax 原理强依赖于球面约束提供的旋转不变性和球面矩闭式。对于单纯形、立方体等其他约束域的扩展，论文未加讨论。一个自然的开放问题是如何在更广的可行域上构建类似的辅助多项式。

  3. ε=Ω(1)\varepsilon=\Omega(1) 时的差距：论文明确指出，对常数级别的完备-可靠性间隙（ε=Ω(1)\varepsilon=\Omega(1)），当前的次指数算法并非已知最优；不排除存在拟多项式甚至多项式时间算法的可能性（见注 3.9）。

  4. 应用范围的广度：论文展示了三个代表性应用，但作者也坦承"argmax 原理的适用范围可能超出所讨论的清晰球面设置"。验证该方法在混合优化、鲁棒矩估计、张量主成分分析等更复杂问题中的有效性仍是未来的任务。

  5. 数值稳定性：所有分析建立在实算术的 SDP 求解模型上。将 SoS 松弛有效实现并处理浮点误差仍是一个实际的工程挑战，论文未涉及此方面。