高阶光滑非凸优化中尖锐的一阶下界

# 高阶光滑非凸优化中的尖锐一阶下界 来源：https://arxiv.org/html/2606.05438 Dongruo Zhou ###### 摘要 我们研究在目标函数满足高阶光滑性假设时，通过确定性一阶算法寻找 \\(\\epsilon\\) 平稳点的复杂度。尽管在仅有 Lipschitz 梯度条件下，经典 \\(\\epsilon^{-2}\\) 速率是最优的，但高阶光滑性可带来加速的一阶上界，最著名的是在 Lipschitz Hessian 条件下的 \\(\\epsilon^{-7/4}\\) 速率，以及在 Lipschitz 三阶导数条件下的 \\(\\epsilon^{-5/3}\\) 速率。然而，匹配的下界一直悬而未决。我们通过为高阶光滑非凸函数证明一个新的无量纲一阶下界来填补这一空白，该下界对任意有限光滑阶数均成立。特别地，我们的构造在 Hessian-Lipschitz 情形下给出了匹配的 \\(\\Omega(\\epsilon^{-7/4})\\) 下界，在三阶光滑情形下给出了匹配的 \\(\\Omega(\\epsilon^{-5/3})\\) 下界。该困难实例基于一种 **区块链** 机制，该机制在保持标量困难实例所需的光滑性结构的同时，强制逐块揭示 oracle。该下界构造在 ChatGPT 5.5 Pro 的辅助下被发现，随后由作者验证。 ## 1 引言 寻找近似平稳点是光滑非凸优化中的基本任务之一。给定可微目标函数 \\(f\\)，目标是找到一点 \\(x\\) 使得 \\(\\|\\nabla f(x)\\| \\leq \\epsilon\\)。我们关注一阶方法，即仅查询函数值和梯度的方法，因为它们是大规模非凸优化中最广泛使用的方法。对于具有 \\(L_1\\)-Lipschitz 梯度和初始间隙 \\(\\Delta\\) 的函数，梯度下降在 \\(O(\\Delta L_1 \\epsilon^{-2})\\) 次一阶 oracle 调用内找到这样的点。该速率在仅有梯度 Lipschitz 条件下是悲观最优的，因此在一般光滑函数类中，除了经典的 \\(\\epsilon^{-2}\\) 依赖外，没有加速空间。 表 1：已知的高阶光滑性下无量纲确定性一阶 oracle 复杂度。仅展示对 \\(\\epsilon\\) 的依赖。 | \\(p=1\\) | \\(p=2\\) | \\(p\\geq 3\\) | |---|---|---| | 上界 | \\(\\epsilon^{-2}\\)（梯度下降） | \\(\\epsilon^{-7/4}\\) [2 (https://arxiv.org/html/2606.05438#bib.bib22), 8 (https://arxiv.org/html/2606.05438#bib.bib23), 23 (https://arxiv.org/html/2606.05438#bib.bib11), 33 (https://arxiv.org/html/2606.05438#bib.bib12), 7 (https://arxiv.org/html/2606.05438#bib.bib3), 24 (https://arxiv.org/html/2606.05438#bib.bib10), 27 (https://arxiv.org/html/2606.05438#bib.bib13)] | \\(\\epsilon^{-5/3}\\) [7 (https://arxiv.org/html/2606.05438#bib.bib3)] | | 下界 | \\(\\epsilon^{-2}\\) [9 (https://arxiv.org/html/2606.05438#bib.bib2)] | \\(\\epsilon^{-12/7}\\) [10 (https://arxiv.org/html/2606.05438#bib.bib1)] | \\(\\epsilon^{-8/5}\\) [10 (https://arxiv.org/html/2606.05438#bib.bib1)] | | 本文结果 | | \\(\\bm{\\epsilon^{-7/4}}\\)（定理 5.2 (https://arxiv.org/html/2606.05438#S5.Thmtheorem2)） | \\(\\bm{\\epsilon^{-5/3}}\\)（定理 5.2 (https://arxiv.org/html/2606.05438#S5.Thmtheorem2)） | 寻求更快速率的一个自然途径是对目标函数施加高阶光滑性。第一个也是最重要的情形是二阶光滑性，即 Hessian 的 Lipschitz 连续性：它是除梯度 Lipschitz 之外最弱的标准假设，用于控制曲率变化，并为算法提供足够结构以区分类凸区域和真正的非凸区域。在此假设下加速的算法证据来自几个相关的 oracle 模型和目标保证。一系列工作使用 Hessian-向量乘积来获得曲率感知的保证，通常以找到近似局部极小值为更强目标。例如，Agarwal 等人 [2 (https://arxiv.org/html/2606.05438#bib.bib22)] 近似求解三次正则化子问题，并在 \\(O(\\epsilon^{-7/4})\\) 次 Hessian-向量乘积复杂度内找到近似局部极小值。在另一个基于 Hessian-向量乘积的加速框架中，Carmon 等人 [8 (https://arxiv.org/html/2606.05438#bib.bib23)] 获得了寻找一阶平稳点的 \\(O(\\epsilon^{-7/4})\\) 复杂度。在一阶逃逸鞍点文献中，基于加速和负曲率的梯度方法在 Hessian-Lipschitz 设定下给出了 \\(O(\\epsilon^{-7/4})\\) 的复杂度界 [23 (https://arxiv.org/html/2606.05438#bib.bib11), 33 (https://arxiv.org/html/2606.05438#bib.bib12)]。 与我们设定最接近的工作同时保持了纯一阶的 oracle 和目标。Carmon 等人 [7 (https://arxiv.org/html/2606.05438#bib.bib3)] 提出的加速“假定凸性直至被证伪”框架在表现为凸性的区域运行加速梯度，并将凸性失败作为非凸景观中进展的凭证，在 Lipschitz Hessian 下给出了 \\(O(\\epsilon^{-7/4}\\log(1/\\epsilon))\\) 的一阶复杂度，在 Lipschitz 三阶导数下给出了 \\(O(\\epsilon^{-5/3}\\log(1/\\epsilon))\\) 的复杂度。后续工作在两个方向上完善了这一图景：重启加速梯度在 Hessian-Lipschitz 情形下去除了对数因子 [24 (https://arxiv.org/html/2606.05438#bib.bib10)]，而无参数加速方法在不需相同光滑性参数调优的情况下恢复了 \\(O(\\epsilon^{-7/4})\\) 复杂度 [27 (https://arxiv.org/html/2606.05438#bib.bib13)]。Jiang 等人 [20 (https://arxiv.org/html/2606.05438#bib.bib14)] 给出了一种纯梯度的拟牛顿方法，其复杂度为 \\(O(d^{1/4}\\epsilon^{-13/8})\\)，在低维中改进了 \\(\\epsilon\\) 依赖，但具有显式的维度依赖而非无量纲保证。 因此，即使算法只观察函数值和梯度，高阶光滑性确实允许超越 \\(\\epsilon^{-2}\\) 的加速。匹配的无量纲下界的缺失已在后续工作中被明确指出，这些工作锐化或重新诠释了上界图景：即使在去除对数因子之后，甚至在在线学习视角恢复了部分上界图景之后，无量纲确定性一阶下界仍未改变 [24 (https://arxiv.org/html/2606.05438#bib.bib10), 15 (https://arxiv.org/html/2606.05438#bib.bib16)]。尽管上界取得了这些进展，但加速速率是否最优仍不清楚。在下界方面，之前最好的结果归功于 Carmon 等人 [10 (https://arxiv.org/html/2606.05438#bib.bib1)]，他们在 Hessian-Lipschitz 设定下证明了 \\(\\Omega(\\epsilon^{-12/7})\\) 下界，并对任意光滑函数证明了 \\(\\Omega(\\epsilon^{-8/5})\\) 下界。这在 Hessian-Lipschitz 情形下留下了指数差距 \\(1/28\\)（介于 \\(12/7\\) 和 \\(7/4\\) 之间），相对于 Lipschitz 三阶导数下的 \\(5/3\\) 一阶速率则留下了指数差距 \\(1/15\\)。这些差距反映了已知下界构造的局限性还是真正的分离，一直是一个长期悬而未决的问题。这引出了以下问题。 **当高阶光滑性可用时，寻找 \\(\\epsilon\\) 平稳点的最优一阶 oracle 复杂度是多少？** 在本文中，我们通过证明一个新的下界来回答这个问题，从而解决了确定性一阶 oracle 复杂度中长期存在的开放差距。我们的贡献如下。 - • 如表 1 (https://arxiv.org/html/2606.05438#S1.T1) 所总结，我们为高阶光滑非凸函数给出了一种新的无量纲一阶下界构造，该构造对任意有限光滑阶数 \\(p\\) 均有效。在 Hessian-Lipschitz 情形下，该构造给出了匹配的 \\(\\Omega(\\epsilon^{-7/4})\\) 依赖，填补了先前 \\(\\epsilon^{-12/7}\\) 下界与已知最佳一阶上界之间的差距。在 Lipschitz 三阶导数下，它给出了三阶光滑情形下匹配的 \\(\\Omega(\\epsilon^{-5/3})\\) 依赖。完整定理追踪了对 \\(\\Delta, L_1, \\ldots, L_p\\) 以及有效光滑约束的依赖。 - • 技术上，我们引入了一种区块链困难实例，该实例用一个**线性算子**进行观测，以增强标量转移问题。非凸势在通过一个线性读出后应用，该读出的算子范数提供了一个额外的旋钮来校准高阶光滑性，同时保留标量残差证书。为了使这种拉回与一阶揭示兼容，每个标量坐标被替换为一个链块：先前的标量状态通过一个入口坐标进入，而当前标量状态通过一个后缀投影读出。这种分离使得尊重零的方法只能逐层揭示构造，从而产生块层尾部隐藏特性和在到达隐藏尾部之前的梯度下界。 #### 符号说明。对于 \\(n \\in \\mathbb{N}\\)，记 \\([n] = \\{1, \\ldots, n\\}\\)。我们用 \\(\\langle \\cdot, \\cdot \\rangle\\) 表示欧几里得内积，\\(\\|\\cdot\\|\\) 表示向量的欧几里得范数以及矩阵的诱导算子范数，并用 \\(\\operatorname{supp}(x)\\) 表示向量 \\(x\\) 的支撑集。向量 \\(e_1, e_2, \\ldots\\) 表示周围欧几里得空间中的标准基向量；当维度重要时，我们记 \\(e_j^{(m)} \\in \\mathbb{R}^m\\)。对于 \\(C^q\\) 函数 \\(f\\)，\\(D^q f(x)\\) 表示其在 \\(x\\) 处的 \\(q\\) 阶 Fréchet 导数，视为一个对称的 \\(q\\)-线性形式。对于 \\(q\\)-线性形式 \\(A\\)，我们记 \\(\\|A\\|_{\\rm op} := \\sup_{\\|v_1\\|, \\ldots, \\|v_q\\| \\leq 1} |A[v_1, \\ldots, v_q]|\\)。对于欧几里得空间之间的映射 \\(G\\)，\\(\\operatorname{Lip}(G)\\) 表示其关于诱导欧几里得范数的全局 Lipschitz 常数；特别地，\\(\\operatorname{Lip}(D^q f)\\) 使用上述 \\(q\\)-线性形式的算子范数。记号 \\(a \\lesssim b\\) 表示 \\(a \\leq C b\\) 其中 \\(C\\) 是一个正的绝对常数，\\(a \\gtrsim b\\) 表示 \\(b \\lesssim a\\)，而 \\(a \\asymp b\\) 表示同时有 \\(a \\lesssim b\\) 和 \\(b \\lesssim a\\)。我们使用 \\(O(\\cdot)\\)、\\(\\Omega(\\cdot)\\) 和 \\(\\Theta(\\cdot)\\)，并约定除非另有明确说明，隐藏常数是正且绝对的。下面引入的命名数值常数，例如标量原始界中的常数 \\(\\ell_q\\)，将在定量速率中明确显示，而不是吸收到这种渐近记号中。 ## 2 相关工作 围绕一阶非凸优化和高阶光滑性的文献非常广泛，因此我们只讨论与我们下界结果最直接相关的部分；以下参考文献具有选择性。 #### 高阶 oracle 模型。 另一系列工作研究能够查询高阶导数信息（而不仅仅是函数值和梯度）的算法。经典的信任域方法和正则化牛顿方法构成了基本的二阶工具箱 [14 (https://arxiv.org/html/2606.05438#bib.bib9), 11 (https://arxiv.org/html/2606.05438#bib.bib6)]。在 Hessian-Lipschitz 设定下，三次正则化构建了一个带三次惩罚项的局部二次模型，并实现了寻找一阶平稳点的 \\(O(\\epsilon^{-3/2})\\) 复杂度 [28 (https://arxiv.org/html/2606.05438#bib.bib4), 11 (https://arxiv.org/html/2606.05438#bib.bib6)]；相关工作还描述了达到二阶平稳点的复杂度 [12 (https://arxiv.org/html/2606.05438#bib.bib7)]。更一般地，正则化的 \\(p\\) 阶泰勒方法在 Lipschitz \\(p\\) 阶导数下实现了 \\(O(\\epsilon^{-(p+1)/p})\\) [6 (https://arxiv.org/html/2606.05438#bib.bib5)]，而对二阶方法的悲观情况分析进一步阐明了该 oracle 模型的最优性 [13 (https://arxiv.org/html/2606.05438#bib.bib8)]。这些速率与访问高达 \\(p\\) 阶导数的算法匹配的下界 [9 (https://arxiv.org/html/2606.05438#bib.bib2)] 一致。最近的混合 oracle 工作进一步研究了梯度和 Hessian 查询之间的权衡；特别是，有限差分 Hessian 近似产生了改进的低维梯度复杂度，甚至少量的 Hessian 查询也可以改变梯度查询指数 [1 (https://arxiv.org/html/2606.05438#bib.bib21)]。这一高阶 oracle 理论与我们的设定互补：我们对目标函数施加高阶光滑性，但算法仍保持一阶。 #### 随机、有限和与局部极小值变体。 Oracle 复杂度文献中还存在大量的随机、有限和与近似局部极小值对应部分。对于二阶平稳性，早期的随机逃逸鞍点结果表明，带噪声或扰动的梯度方法可以避免严格鞍点并达到近似局部极小值 [19 (https://arxiv.org/html/2606.05438#bib.bib26), 21 (https://arxiv.org/html/2606.05438#bib.bib27), 22 (https://arxiv.org/html/2606.05438#bib.bib28)]。在 Hessian-Lipschitz 结构下，Hessian-向量和纯梯度算法通过三次正则化、加速逃逸鞍点和负曲率提取获得了更快的近似局部极小值保证 [2 (https://arxiv.org/html/2606.05438#bib.bib22), 8 (https://arxiv.org/html/2606.05438#bib.bib23), 23 (https://arxiv.org/html/2606.05438#bib.bib11), 33 (https://arxiv.org/html/2606.05438#bib.bib12), 3 (https://arxiv.org/html/2606.05438#bib.bib25), 26 (https://arxiv.org/html/2606.05438#bib.bib29), 30 (https://arxiv.org/html/2606.05438#bib.bib30)]。随机和有限和优化将扰动 SGD、方差缩减、随机三次正则化和三阶光滑性相结合，以改进局部极小值发现的样本或梯度复杂度 [31 (https://arxiv.org/html/2606.05438#bib.bib24), 17 (https://arxiv.org/html/2606.05438#bib.bib31), 18 (https://arxiv.org/html/2606.05438#bib.bib32), 25 (https://arxiv.org/html/2606.05438#bib.bib33), 29 (https://arxiv.org/html/2606.05438#bib.bib34), 32 (https://arxiv.org/html/2606.05438#bib.bib35), 36 (https://arxiv.org/html/2606.05438#bib.bib36), 37 (https://arxiv.org/html/2606.05438#bib.bib37), 34 (https://arxiv.org/html/2606.05438#bib.bib38), 38 (https://arxiv.org/html/2606.05438#bib.bib39)]。最近，一个在线到非凸转换的观点通过一个通用框架给出了确定性和随机上界 [15 (https://arxiv.org/html/2606.05438#bib.bib16)]。在下界方面，Arjevani 等人 [4 (https://arxiv.org/html/2606.05438#bib.bib18)] 刻画了随机 Hessian-向量和高阶 oracle 的能力与局限性，表明二阶信息无法像在确定性优化中那样消除固有的随机障碍。在有限和模型中，Emmenegger 等人 [16 (https://arxiv.org/html/2606.05438#bib.bib19)] 开发了高阶光滑非凸目标的下界，随后由 Zhou 和 Gu [35 (https://arxiv.org/html/2606.05438#bib.bib20)] 将其锐化为无量纲形式。在有界方差随机梯度模型中，Arjevani 等人 [5 (https://arxiv.org/html/2606.05438#bib.bib17)] 证明了紧的下界，表明 SGD 在寻找一阶平稳点方面是极小值最优的，而更强的均值