精读笔记

Problem Setting

论文研究的是确定性零阶凸优化中 exact function value 的最坏情形查询复杂度。目标类是欧氏球上的 1-Lipschitz 凸函数，算法只能看到 f(x) 的精确实数值，没有梯度、次梯度、比较 oracle 或有限精度限制。

真正困难点在于 exact value 是一个很强的 oracle：一个实数响应原则上可以携带无限信息，算法也允许任意不连续地依赖过去值。因此常规信息论 bit-counting、memory lower bound、rounded transcript 都不能直接用。以前卡住的地方正是这里：一阶 oracle 的 Nemirovski-Yudin 下界只给 Ω(d)，而 value-only 的 Protasov 上界是近 O(d^2)。缺的是一个能在 exact-real 模型下证明“函数值仍然不足以高效提供方向信息”的机制。

这篇论文的关键矛盾是：函数值比一阶信息弱，但 exact value 又太强，不能按有限信息处理。作者要证明的是，即使给无限精度值和无限计算，缺少 subgradient/separating direction 仍然带来近二次查询代价。

Motivation

已有路线不够的原因很明确。第一，从一阶 oracle 继承下界只会低估 value-only 的困难，因为一阶响应包含方向信息，而函数值不包含。第二，memory-query tradeoff 看似能给 superlinear lower bound，但它依赖 bit memory；exact value transcript 无法压缩成 O(T polylog d) bits，除非额外证明稳定量化，而这里算法可不连续。第三，随机 zeroth-order 或 noisy bandit 模型的 minimax 结论不适用，因为这篇研究的是 deterministic、noiseless、exact-real、nonsmooth worst case。

作者的核心观察是：不要试图限制每个函数值携带多少 bit，而要构造一个 adversarial transcript，使得无论 exact responses 多么精确，它们都只强制某些 affine pieces 满足局部等式/不等式，同时大量 row-level uncertainty 仍以 Cartesian product 形式保留。缺口不是“如何量化一个值的信息量”，而是“如何在 exact transcript 下保留足够多的全局凸函数兼容性”。

Core Idea

核心思想是把 hard functions 组织成一族 max-affine support functions：f_W(x,z)=max_i {a x_i + <w_i,z>}。这里 W 的每一行 w_i 是一个隐藏 row，函数值查询只看到这些 affine pieces 的最大值。adversary 对每一行维护一个凸不确定集 P_i，并保证一个很强的 invariant：任意从 P_1,...,P_m 中独立选 row 得到的 W，都产生完全相同的查询 transcript。

这改变了下界建模方式。传统 resisting oracle 往往给出局部一致的回答，再证明可扩展；这里直接维护一个 product family of globally valid convex functions。每次查询要么让一个 row 通过等值切片精确解释返回值，要么对多个 row 做小体积浅截断。这样 exact value 的无限精度不再是漏洞，因为响应不是被编码成 bit，而是被吸收到几何约束中。

本质区别在于，它把“算法学到了什么”从 transcript 信息量转成“row uncertainty 的维度和体积损失”。只要查询少于 d^2/log d，仍有线性多个 row 保持高维、大体积；这些 row 的宽度可以沿一个公共方向累加，最终产生两个函数值完全不可区分、但 minimizer 相距常数的实例。

Method

1. Hard family：使用 d=2m，变量分成 x 和 z。每个函数是 m 个 affine forms 的最大值，斜率为 (a e_i, w_i)。这保证凸性、Lipschitz 性和 f(0)=0，同时让优化解由支持多面体 K_W=conv{(a e_i,w_i)} 到原点的最近点 p_W 决定。需要这一结构，是因为 minimizer separation 可以被转化为 closest-point direction separation。

2. Support-function geometry：f_W 在球上的唯一 minimizer 是 -p_W/||p_W||，且有 growth inequality：离 minimizer 的平方距离会带来约 ||p_W|| 的 objective gap。由于 ||p_W||≈1/sqrt(m)，只要两个 minimizer 相距常数，就能得到 Ω(1/sqrt d) 误差。这里的关键变化是把函数优化下界变成几何方向识别下界。

3. Exact resisting oracle：对每个 row 维护 P_i。查询 (x_t,z_t) 给每个 row 定义 affine functional ℓ_i(w)=a x_{t,i}+<w,z_t>。adversary 选择 quantile level，若有非平凡 row 承担最大值，则将该 row 切到等值截面，其余 row 保留在半空间下方；否则做 noninformative shallow truncation。这个机制解决 exact transcript consistency：所有最终 W 都精确复现所有响应。

4. Dimension-volume accounting：每个 informative query 至多消耗一个 row 的一个维度；每次 query 只造成受控体积损失。T≤η m^2/log m 时，至少 m/2 个 row 仍然高维且 normalized volume radius 为常数级。这一步不是装饰性技术，而是把 query budget 映射成 residual geometric uncertainty。

5. Aggregate width to indistinguishable minimizers：用 Urysohn inequality 从体积半径推出平均宽度，再通过随机方向平均找到一个公共方向，使好 row 的总宽度 Ω(mτ)。沿该方向取每个好 row 的两端，构造 W^+ 和 W^-。由于 barycentric 权重几乎均匀，row displacement 不会被投影最近点时抵消，最终 normalized p_W^+ 和 p_W^- 相距常数。

Key Insight / Why It Works

最核心贡献是 exact Cartesian-product uncertainty invariant。它绕过了 exact real value 的无限信息问题：不需要证明一个值只能传几 bit，而是证明 adversary 可以选择值，使得大量独立 row choices 仍全部精确兼容 transcript。这是本文相对于 memory/communication 路线的实质创新。

第二个关键 insight 是 row-wise max-affine family 的几何设计。a e_i 这一块强制 closest-point barycentric weights 接近 uniform；w_i 这一块承载隐藏方向。τ=Θ(1/sqrt m) 的尺度选择让两个需求同时成立：斜率仍小于 1，且 row 平均位移能在 p_W 的 z-block 中产生与 ||p_W|| 同阶的角度扰动。如果没有近均匀 barycentric 结构，aggregate width 可能在求最近点时被稀疏权重或重新加权吃掉。

第三个有效点是体积到宽度的转换。查询过程可能以很多细碎半空间削掉不确定集，单看某一行可能很难追踪形状；作者用 normalized volume radius 和 Urysohn inequality 只保留足够粗的 convex-geometric 量。这个步骤更像一个 robust potential argument，而不是 engineering。

哪些部分可能只是辅助：常数选择、ε0=10^-7、Γ=100、K=708 这类数值基本是 proof bookkeeping；混合整数 lift 也是重要 consequence，但核心数学创新仍在连续 lower bound。Protasov 上界不是本文新算法，因此 closing gap 的上界侧主要依赖已有结果。

这不是 scaling / data / benchmark 型结果；它是一个 oracle-model lower bound。若要类比机器学习术语，真正的新 inductive bias 是把 exact transcript 的信息流重组为“row product uncertainty + support-function geometry”。

Relation To Prior Work

最接近的谱系有三条。第一是 Nemirovski-Yudin 一阶 oracle complexity，但那条线给的是 Ω(min{d,ε^-2})，在 ε≈d^-1/2 时只有 Ω(d)，无法区分 value-only 和 full first-order。本文证明两者在同一 nonsmooth Lipschitz class 上存在 polynomial separation：full first-order 是 Θ(d)，exact value-only 是近 Θ(d^2)。

第二是 Protasov 的 deterministic value-only 上界。本文不是改进上界，而是证明 Protasov 的近二次维度依赖基本不可避免。这一点很重要：它把一个长期算法上界从“也许很松”变成“除了 log 因子外正确”。

第三是近期 memory-query tradeoff 和 finite-bit / inner-product oracle lower bounds。本文与它们的本质差异是没有把 value transcript 压缩成有限 bits，也没有依赖 memory restriction。exact real oracle 下的下界必须处理不连续 adaptivity，这正是 Cartesian-product invariant 的作用。

混合整数部分则属于 transfer-theorem 谱系。新意不是简单套用，而是先把连续 hard family 修成 common optimal value 和 full box domain，再做 2^n lift。这个结果说明 continuous value-only difficulty 与 integer enumeration difficulty 可以乘法叠加。

Dataset / Evaluation

这篇论文没有 dataset 或 empirical evaluation；评价标准是 theorem 是否覆盖声明的 oracle model。就核心 claim 而言，证明覆盖了最强的 deterministic exact-value setting：无限计算、无限精度、可不连续 query map、输出不必是 queried point。因此 evaluation 与 claim 的匹配度高于实验型论文。

但验证范围也很窄：只验证 worst-case nonsmooth convex Lipschitz class，不说明实际 derivative-free 优化算法在常见结构化目标上的表现，也不覆盖 randomized algorithms、smooth objectives、strong convexity 或 stochastic/noisy feedback。Lean formalization 只覆盖较弱精度版本；主 theorem 的凸几何链条没有形式化验证。AI-assisted proof development 被披露，但不是独立 evidence。

Limitation

主要限制不是常数或写法，而是适用边界。

第一，结果强依赖 deterministic transcript。resisting oracle 需要根据算法查询自适应维护 compatible product set；这不直接给 randomized minimax lower bound，也不产生一个 hard distribution。

第二，hard family 是 nonsmooth max-affine。它证明了没有 smoothness 假设时 value-only 确实近二次困难，但不能推出 smooth 或 strongly convex value-only 同样困难。若实际问题带有平滑结构，有限差分和模型拟合可能显著改变复杂度。

第三，精度尺度绑定在 Θ(d^-1/2)。构造中的 optimum depth 也是这个量级，所以常数精度下是否仍有近二次 gap 文中未充分说明；作者也明确提到需要不同构造。

第四，上下界仍有 polylog gap。下界损失来自 volume accounting / Urysohn / query budget 的 log，还是 Protasov 上界中的 log 是真实瓶颈，文中未充分说明。增益来源清楚是几何不确定性保持，但 log 因子归因仍不清。

第五，混合整数 lift 依赖 transfer theorem 和 common-optimum preprocessing。它说明复杂度乘法叠加，但并不等于给出了新的混合整数算法机制；上界本质上仍是枚举 binary fibers 加 Protasov。

Takeaway

• 1. exact function value 不等于接近 first-order information。
• 即使实数值无限精确，缺少方向信息也会在 deterministic nonsmooth convex optimization 中造成近 d 倍额外查询代价。
• 2. 做 exact-oracle lower bound 时，正确对象不是 transcript entropy，而是 transcript-compatible function family 的几何残余。
• Cartesian-product uncertainty 是可以迁移的 proof pattern，尤其适合处理“一个响应可能含无限信息”的 oracle。

一句话总结

《Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization》把 deterministic exact-value convex optimization 的维度复杂度从 Ω(d) 推到近 Ω(d^2)，核心贡献是用 Cartesian-product resisting oracle 和 support-function geometry 证明精确函数值仍无法替代一阶方向信息。