🔢 mathematics

Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization: A Near-Quadratic Lower Bound from Exact Function Values

本文通过为精确函数值建立 $\Omega(d^2/\log d)$ 的近二次方下界，填补了无导数凸优化确定性查询复杂度领域长期存在的空白，从而在多项式对数因子范围内使之与目前已知的最佳上界相匹配，并将该结果扩展到了混合整数设定中。

原作者： Phillip Kerger

发布于 2026-07-16

📖 1 分钟阅读🧠 深度阅读

原作者： Phillip Kerger

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图在一个雾气弥漫的广阔山谷中寻找最低点。你看不见地面，也没有地图。你唯一的工具是一个神奇的传感器，当你把它放在地上时，它能告诉你那个特定位置的确切高度。你想尽可能快地找到山谷的底部。但你看不出坡度，也看不出山丘的方向；你只能得到一个数字：“这里的高度是100英尺。”这就是**无导数优化（derivative-free optimization）**的世界。在科学和工程领域，我们经常面临这样的问题：我们无法计算一个系统是如何变化的（即“导数”或斜率），因为该系统是一个黑箱、一个复杂的模拟过程或是一次物理实验。我们必须依赖试错法，不断询问系统：“如果我这样做，会发生什么？”并得到一个精确的答案。

几十年来，数学家们一直在争论到底需要多少次这样的“高度检查”才能保证找到底部。如果你也能询问斜率（哪边是下坡？），你就能非常快地找到底部。但如果你只被允许询问高度，规则就变了。直到现在，我们对这一领域的理解还存在巨大的鸿沟。一些聪明的算法暗示你可能需要进行大量的检查（大约是维度的平方），而最好的理论证明则认为你只需要与维度相等的次数。这就像是一组人说：“你需要检查足球场上的每一个平方英寸，”而另一组人说：“你只需要检查几个点。”这篇论文介入其中，解决了这一争议，证明了“足球场”的估算比“几个点”的想法要接近真相得多。

这篇题为《填补无导数凸优化的预言机复杂度差距》（Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization）的论文，由菲利普·克格尔（Phillip Kerger）撰写，处理的正是一个完全相同的谜题。作者在先进人工智能工具的大力帮助下，证明了当你受限于仅使用精确的高度值（不允许使用斜率）来寻找一个非光滑、碗状函数（具体来说，是一个由平坦的线性部分拼接而成的函数）在高维空间中的最小值时，你必须做比以前认为的更多的功课。具体而言，该论文建立了一个新的、更强的下界：你需要的检查次数大约随维度的平方增长（数学上写作 $\tilde{\Omega}(d^2)$ ），而不是仅仅呈线性增长。

为了理解这为什么重要，请把“维度”想象成你必须调节的机器旋钮的数量。如果你有10个旋钮，旧的、较弱的证明暗示你可能只需要检查大约10或20次设置。而新的证明表明，在最坏的情况下，你实际上可能需要检查数百甚至数千次设置（大约是 $10^2$ 或更多）。作者构建了一个巧妙的“对抗性”场景，其中一个狡猾的计算机程序（预言机）会以一种让你始终处于猜测状态的方式来回答你的问题。通过仔细分析每个答案实际上提供了多少信息，论文证明了“无斜率”方法本质上比“感知斜率”的方法要慢得多。

该论文还将这一发现扩展到了一个更复杂的场景，称为混合整数优化（mixed-integer optimization）。想象一下，你的山谷不仅有连续的旋钮（比如音量旋钮），还有只能开启或关闭的开关（比如电灯开关）。论文证明，寻找底部的难度会成倍增加：如果你有 $n$ 个开关和 $d$ 个旋钮，你需要的检查次数会爆炸式增长到大约 $2^n \times d^2$ 。这意味着，即便只是增加几个开关，也会在旋钮本身已有的二次方难度之上，让问题变得呈指数级困难。

至关重要的是，这篇论文并不只是在猜测；它提供了一个严密的数学证明。它排除了任何精巧的、确定性算法能够仅凭精确值就神奇地绕过这个二次方障碍的可能性。作者甚至使用了形式化验证软件（一种逐行检查数学证明的工具）来确保逻辑成立，并且他们公开承认现代人工智能在发现该证明过程中发挥了重要作用。其结果填补了自1996年以来一直存在的数学知识空白，表明当你对问题的斜率“视而不见”时，你确实必须为额外的等待时间和精力付出代价。

技术摘要：弥合无导数凸优化的 Oracle 复杂度差距

问题陈述
本文研究了在仅使用精确函数值（零阶 Oracle）的情况下，最小化 $d$ 维欧几里得球体 ( $B_d$ ) 内凸且 1-Lipschitz 函数的确定性查询复杂度。研究重点是寻找 $\varepsilon$ -近似解所需的 worst-case 查询次数，特别是在精度为 $\varepsilon = \Theta(d^{-1/2})$ 的情况下。

在此项工作之前，该设定在文献中存在显著的多项式差距：

下界： 已知的最佳下界为 $\Omega(d)$ ，这继承自更强的阶一 Oracle 模型（其中亚梯度可用）。
上界： Protasov (1996) 的确定性方法在达到相同精度时需要 $O(d^2 \log^2 d)$ 次评估。

本研究探讨的核心问题是：缺乏导数信息是否会从维度 $d$ 的线性复杂度根本性地增加到二次方，或者 $\Omega(d)$ 的界限是否是紧致的。

方法论
作者构建了一个“困难函数族”和一个“抵抗性 Oracle”来建立近二次方的下界。证明过程分为四个主要部分：

困难函数族： 作者定义了一类函数 $f_W(x, z) = \max_{i \in [m]} \{ ax_i + \langle w_i, z \rangle \}$ ，其中 $m = d/2$ ，且 $x, z \in \mathbb{R}^m$ ，行向量 $w_i$ 是半径为 $\tau = \Theta(m^{-1/2})$ 的小球内的向量。这些函数是凸且 1-Lipschitz 的。这些函数的最小化点由原点到定义线性分片的向量构成的凸包的欧几里得投影决定。
精确抵抗性 Oracle： 作者并非提供单个函数，而是维护一个“矩形”不确定集 $P_1 \times \dots \times P_m$ ，其中每个 $P_i$ 是可能行向量的紧致凸集。其不变性在于：从这些集合中进行任何行选择产生的函数，都与整个查询历史的响应保持一致。
- 当算法查询一点时，对抗者分析每个行集在查询点上的仿射泛函。
- 如果某一行是非常数的，对抗者通过超平面切割集合（降低 1 维），但确保剩余集合保留其内在体积的显著比例。
- 如果所有相关行都是常数，对抗者返回常数值而不降低维度。
聚合宽度与不可区分性： 证明过程追踪了所有行集中的总余维数以及内在体积的对数损失。在经过 $T = O(m^2 / \log m)$ 次查询后，分析表明仍有线性数量的行集保持高维且具有较大的归一化体积。利用 Urysohn 不等式和平均值论证，作者识别出了一个在方向 $\theta$ 上，这些剩余集合的聚合宽度是较大的方向。
最小化点的分离： 通过选择行集在方向 $\theta$ 上的极值点，对抗者构造了两个不同的函数 $f_{W^+}$ 和 $f_{W^-}$ ，它们对算法而言是不可区分的（产生相同的记录）。然而，由于投影具有“近似均匀”的重心结构（引理 8），行的聚合位移迫使这两个函数的唯一最小化点之间保持常数距离。因此，算法的任何单一输出都必须与至少一个函数的真实最小化点相距较远，从而导致 $\Omega(d^{-1/2})$ 的误差。

核心贡献与结果

近二次方下界： 主要结果（定理 1）确立了对于精度 $\varepsilon = \Theta(d^{-1/2})$ ，确定性精确值复杂度为 $\tilde{\Omega}(d^2)$ 。具体而言，存在常数使得：
$c \frac{d^2}{\log(d+1)} \leq Q_{\text{val}}^{\text{det}}\left(d, \frac{\varepsilon_0}{\sqrt{d}}\right) \leq C d^2 \log^2(d+1)$
这在多项式对数因子内弥合了上下界之间的差距，证明了仅靠精确值本身比一阶 Oracle（其为 $\Theta(d)$ ）的信息量显著减少。
混合整数扩展： 利用来自 Basu 等人的转移定理，作者将此结果提升到包含 $n$ 个二进制变量和 $d$ 个连续变量的混合整数凸优化问题。他们证明了复杂度随整数维度成乘性比例缩放：
$Q_{\text{MI,val}}^{\text{det}}(n, d, \varepsilon) = \tilde{\Theta}(2^n d^2)$
即使允许在乘积域内的任意分数点进行查询，该结论依然成立。
形式化验证： 作者承认在开发数学论证过程中广泛使用了 AI 工具 (GPT-5.6 Sol Pro)。为了确保严谨性，他们使用 Lean 编程语言对 $\tilde{\Omega}(d^2)$ 下界证明进行了形式化验证。

意义与主张
该论文声称解决了自 1996 年以来的复杂度差距。其意义在于隔离了在无噪声、精确实数设定下，由于缺乏亚梯度信息而产生的代价。作者强调，这种分离并非由于有限精度或内存限制造成的伪影，而是精确函数值与一阶 Oracle 提供的本质信息差异。

这项工作表明，对于非光滑凸优化，“仅值”模型在根本上比一阶模型更难，在维度上需要二次方的查询次数而非线性次数。其证明技术依赖于笛卡尔积不确定性不变性和聚合宽度论证，被呈现为一种在不为精确实数响应分配有限信息内容的情况下，建立部分信息设定下界的新颖机制。

作者对于上下界之间剩余的对数因子保持谦逊，并指出当前的困难函数族依赖于特定的深度 ( $\Theta(d^{-1/2})$ )，这使得关于无维度依赖精度界限以及在平滑性等额外正则性假设下的行为问题仍然开放。

技术摘要：弥合无导数凸优化的 Oracle 复杂度差距

类似论文