On Approximate Computation of Critical Points

技术摘要：论近似计算临界点

问题陈述
本文探讨了寻找非凸函数临界点（梯度为零的驻点）的计算复杂度，特别关注了“近似”计算的可行性。虽然对于三次多项式而言，寻找精确临界点是 NP-hard 的已是共识，但优化领域中存在一种普遍观点，认为寻找近似临界点（即梯度范数较小 $\|\nabla f(x)\| \le \epsilon$ 的点，或接近真实临界点的点 $\|x - x^*\| \le \epsilon$）在计算上应该是可行的。作者对这一直觉提出了挑战，研究了即使是对于简单的非凸函数类（如低阶多项式），粗略的近似临界点是否也能在多项式时间内计算出来。

方法论
作者采用了标准的图灵计算模型，其中输入由参数化函数类（主要是固定阶数的多项式）的系数组成。其核心方法论包括将 团（Clique） 问题（一个已知的 NP 完全问题）通过多项式时间归约到寻找近似临界点的问题上。

关键技术工具包括：

1. 多项式构造： 作者构造了特定的三次和四次多项式（以及多项式与指数函数的乘积），这些多项式的临界点与给定图中的团相对应。一个核心构造是一个四次多项式 $g_{G,C,k}(x)$，其设计使得其根恰好对应于图 $G$ 中的 $k$-团的指示向量。
2. 近似硬度（Hardness of Approximation）： 为了证明近似计算的硬度，作者必须证明：如果一个算法返回的点是一个“接近”临界点的点（就梯度范数或欧几里得距离而言），那么该算法实际上解决了底层的 NP-hard 判定问题。
3. 解析界限： 证明过程高度依赖于对构造多项式行为的界定。这包括：
   • 建立多项式的强制性（coercive）并证明其存在极小值。
   • 使用一阶和二阶必要条件（FONC/SONC）来界定极小值的位置。
   • 应用 Lipschitz 连续性论证，将多项式在接近临界点处的值与其在真实临界点处的值联系起来。
   • 利用一元多项式根的界限（Fujiwara 界限）来约束变量的大小。

主要贡献与结果

本文证明了在几种不同的“近似”定义下以及各种结构性假设下，计算近似临界点是不可行的（除非 P=NP）：

1. $\epsilon$-近似临界点（梯度范数）：

   • 定理 3： 作者证明，除非 P=NP，否则不存在多项式时间算法可以计算出 $n$ 个变量的三次多项式的 $2^n$-近似临界点（其中 $\|\nabla p(x)\| \le 2^n$）。即使当不存在临界点时允许算法返回任意点，该结论依然成立。
   • 推论 8： 该结果扩展到了寻找 $n^d$-近似临界点的伪多项式时间算法。
   • 对唯一临界点的意义： 即使在多项式被承诺具有唯一临界点的情况下，这种硬度依然存在。在这种设定下寻找 $2^n$-近似临界点将反驳植入团猜想（Planted Clique conjecture）并意味着 NP=RP。

2. 结构性假设（下界性与唯一性）：

   • 命题 9： 判定一个三次多项式的指数函数（该函数总是下界的）是否存在临界点是 NP-hard 的。
   • 命题 10： 即使对于保证有临界点且没有“伪临界点”（即每个临界点都是全局最小值）的下界函数，寻找临界点仍然是困难的。这意味着不存在伪局部极小值并不能保证计算的可行性。
   • 定理 11： 对于下界四次多项式，在半径为 $2^n$ 的球体内寻找 $2^n$-近似临界点是 NP-hard 的，即使算法在单位超立方体内不存在临界点时可以表现得任意。

3. $\epsilon$-近临界点（到解的距离）：

   • 定义： $\epsilon$-近临界点是指距离真实临界点距离在 $\epsilon$ 以内的点。
   • 定理 13： 除非 P=NP，否则不存在多项式时间算法可以计算出三次多项式的 $\frac{1}{12000 n^{3.5}}$-近临界点。
   • 定理 15： 该硬度结果扩展到了下界函数（四次多项式与指数函数的乘积），表明寻找 $\frac{1}{1000 n^7}$-近临界点也是不可行的。

意义与主张
本文的主要意义在于颠覆了关于近似临界点计算是易处理任务的普遍认知。作者认为，非凸优化的困难性并不仅仅源于伪局部极小值或鞍点的存在，而是由于定位任何驻点（即使是近似的）这一任务本身具有内在的难度。

• 与 Oracle 模型的对比： 作者将其结果与以往基于 Oracle 模型（例如 Carmon 等人的工作）的研究进行了区分，后者提供了查询复杂度的下界。本文运行在图灵模型下，排除了任何多项式时间算法，包括基于凸松弛或其他非 Oracle 方法的算法。
• 对算法的影响： 这些结果表明，标准的算法如梯度下降法（Gradient Descent）或牛顿法（Newton's method）（以及它们的高阶扩展）无法保证在多项式时间内找到一般三次多项式的即使是粗略的临界点近似。具体而言，论文指出，牛顿法最自然的更高阶扩展（求解三次泰勒展开的临界点）在缺乏计算可行性保证的情况下，其单次迭代复杂度是不可控的（除非 P=NP）。
• 未来方向： 作者谦逊地总结道，其结果旨在激励研究特定的参数化函数类和结构性假设（这些假设应可在多项式时间内检查），从而使近似临界点的计算变得可行。他们指出，虽然凸性允许计算的可行性，但检查 4 次或更高阶多项式的凸性本身也是困难的，这在理解哪些结构属性能实现高效近似方面留下了空白。