平滑非凸零阶优化的下界：低曲率迹条件下确定性的代价

arXiv:2610.27550v1 公告类型：新 摘要：低曲率迹是一种有效秩条件，常用于解释随机化零阶方法为何能够扩展到语言模型微调等高维任务。确定性方法能否获得同样的节省？我们证明不能。我们研究这样的问题：在 \(\mathbb{R}^d\) 上，仅通过精确函数值寻找 \(L\)-smooth 非凸函数的 \(\varepsilon\)-驻点，并假设在初始函数值以下，Hessian 被一个迹不超过 \(LE\) 的固定矩阵所控制；这正是用于解释零阶微调的有效秩条件。当 \(ET\le d\) 时，若拒绝使 \(f\) 增大的步长，零阶微调所使用的 Gaussian two-point method 仅需 \(O(ET)\) 次调用，其中 \(T=L\Delta/\varepsilon^2\) 是梯度下降从初始间隙 \(\Delta\) 出发所需的迭代次数。我们证明，任何随机化方法都需要 \(\Omega(ET)\) 次调用，因此这一成本在常数因子范围内是最优的。相比之下，任何确定性方法都需要 \(\widetilde\Omega(d\min\{T,\sqrt{ET}\})\) 次调用，而 adaptive subspace search 可达到 \(O(d\min\{T,\sqrt{ET}\})\)：确定性方法对于每个发现的方向大约需要 \(d\) 次调用，而迹预算允许发现约 \(\sqrt{ET}\) 个方向。因此，确定性会使成本增加约 \(d/(E+\sqrt{ET})\) 倍（忽略对数因子）；当 \(E\) 和 \(T\) 固定时，该倍数随 \(d\) 线性增长；一旦 \(E\) 超过 \(T\) 一个对数因子，确定性方法就需要 \(\Omega(dT)\) 次调用，与没有任何迹预算时相同。我们的下界对 \(C^\infty\) 函数成立，且矩阵界在整个 \(\mathbb{R}^d\) 上成立，即使每次调用还返回按秩计价的梯度投影。