精读笔记
Problem Setting
论文实际处理的是 exact zeroth-order convex optimization 的 oracle complexity：目标函数是 B_2^d 上的 nonsmooth L-Lipschitz convex function，每次 query 只返回精确标量 f(x)，算法可以 randomized、adaptive。真正困难不在定义 oracle，而在证明“一个精确实数”仍然信息受限。因为 exact value 不是 noisy sample，它可以以非线性方式混合所有隐藏方向；adaptive finite-difference 也可能从多个 values 中重构方向信息。
以前路线卡在两个方向：first-order lower bound 的 zero-chain/span argument 控制的是返回梯度向量的可见子空间，对 scalar value 无法施加类似约束；stochastic zeroth-order lower bound 依赖 observation noise 的 KL / testing argument，但 exact oracle 的 transcript 条件于函数后是确定的。关键矛盾是：scalar feedback 格式低维，但 noiseless real value 的潜在信息量不容易被传统信息论工具上界。
Motivation
已有 upper bound 的多项式尺度已经很清楚：two-point method 给 O(d eps^{-2})，general evaluation-oracle convex optimization 给约 O~(d^2)，合起来是 d min{d,eps^{-2}}。缺的是能匹配这个尺度的 exact-value lower bound。Braun et al. 的 local-oracle lower bound 虽然适用，但只到 eps^{-2}，在 eps≈d^{-1/2} 时只给 d，而 upper bound 已经到 d^2。
作者的核心观察是：不要试图限制 value observation 本身的“bits”，而要限制它对优化所需 latent quantity 的 posterior alignment。对于合适 hard family，算法成功等价于学到一个隐藏 aggregate direction；exact max values 虽然精确，但每次只会有限地移动该 aggregate direction 的 posterior mean。缺口因此从 transcript indistinguishability 转成 posterior geometry。
Core Idea
核心想法是构造 f_Xi(x)=max_i <a_i,x>，其中 a_i 是归一化截断高斯。这个函数的 optimum 通常在 -1/sqrt(k) 尺度，同时任意点都有 f(x) >= (1/k)<sum_i a_i,x>。因此，如果输出点要接近最优，它必须在几何上显著朝向 -s=sum_i a_i。优化问题被重写成：算法能否通过 exact max observations 学到 s。
本质区别是建模方式变了：prior lower bound 多半约束算法可见的 span、support 或 noisy transcript divergence；这里直接跟踪 posterior mean energy ||E[s | transcript]||^2。这个量恰好对应“algorithm has learned usable alignment”的强度。它是一个适合 noiseless adaptive oracle 的信息度量，因为它不需要噪声，也不要求 scalar value 只暴露局部坐标。
Method
第一步是 hard distribution。随机 support function 同时提供两个性质：负的 optimum 规模为 -Theta(k^{-1/2})，以及 pointwise lower bound f(x) >= k^{-1}<s,x>。前者给出目标难度，后者把输出误差下界转成 output 与 s 的 alignment 问题。
第二步是 augmented posterior。真实算法只看 values，但分析中额外暴露 active index，即哪一个 linear piece 达到 max。这样 posterior 不再是混合在不同 winner 上的复杂分布，而是每个 block 独立地被 affine equality 或 halfspace inequality 截断；blockwise product structure 得以保留。这一步是证明可做的关键，不是算法增强。
第三步是 one-step selection bound。给定过去 transcript 后，每个 hidden block 是 affine support 上的 strongly log-concave distribution。一次新的 max observation 选择 winner slice 和 loser tails；作者证明它对 unscaled sum 的 posterior mean movement 的 expected squared norm 只有 O(log k)。然后用 martingale increment orthogonality 累加，得到 E||E[s|G_T]||^2 <= C T log(ek)。缩放回 a_i=b_i/sqrt(d) 后是 C T log(ek)/d。
第四步是 residual tail 与 Yao。posterior mean 小意味着算法没有学到足够 alignment；posterior residual 在任意 transcript-measurable output direction 上仍有 subgaussian tail，防止算法靠 residual 偶然对齐。联合 negative optimum event 后得到 deterministic distributional lower bound，再用 Yao 得到 randomized worst-case lower bound。
Key Insight / Why It Works
最核心贡献是 posterior mean energy，而不是 support function hard family 本身。max-of-linear hard instances 在 convex lower bound 中并不陌生；真正新的是证明 exact adaptive max observations 对 aggregate posterior mean 的能量增长可控。这个视角避开了 exact value model 最麻烦的地方：单个实数可能携带无限精度信息，但它对“优化所需方向”的可用 posterior alignment 仍然增长缓慢。
one-step selection bound 是技术心脏。winner block 被切到一个 affine slice，loser blocks 被 lower-tail conditioning；strong log-concavity 控制这些 conditional barycenters 不会大幅移动。O(log k) 来自 max-selection 的极值/quantile 结构，而不是维度 d。d 的下界因子来自隐藏向量缩放：每个 b_i 是 d 维高斯尺度，a_i=b_i/sqrt(d)，所以 T 次 observation 的 scaled posterior energy 只有 T log k / d。
最可能是核心贡献的部分：augmented posterior product structure + one-step posterior mean movement bound + martingale energy accumulation。这三者组合形成了一个可迁移的 noiseless oracle lower-bound template。negative optimum event、truncated Gaussian spectral event、residual subgaussian tail更像闭合证明所需的几何与概率支撑。
这不是 scaling / data 型增益；它是一个 lower-bound proof architecture。若要类比机器学习术语，它更接近 latent structure identification：优化成功必须识别 latent aggregate direction，而 scalar max observations 对该 latent 的 information gain 被 posterior geometry 限制。
Relation To Prior Work
最接近的上界参照是 Shamir two-point exact value O(d eps^{-2}) 和 Lee-Sidford-Vempala evaluation-oracle O~(d^2)。论文的下界说明这两个 upper-bound regime 的多项式部分不是算法分析松，而是 exact scalar feedback 的内在代价，至少在 nonsmooth Lipschitz worst-case 上成立。
与 stochastic zeroth-order lower bound 的本质差异是：Duchi/Wibisono 线路靠 noisy observation laws 的 testing / divergence；这里没有 oracle noise，不能比较 transcript distributions 的 KL 收缩。与 first-order zero-chain/resisting-oracle 的差异是：那些方法限制梯度返回的 span；这里 value query 可 dense 地依赖所有 hidden vectors，span 控制失效。
与 Braun-Guzman-Pokutta local-oracle lower bound 的关系更微妙：local oracle lower bound 覆盖更强 oracle，因此给出的是更通用但更粗的 eps^{-2} baseline；本文反而利用 scalar-only 的结构，证明额外 d 因子。这是“更专门的 oracle model 允许更强下界”的典型例子。
看似新的部分中，Yao、support-function construction、strong log-concavity tail tools都属于已有思想重组；实质创新是 posterior mean energy method for adaptive exact max observations。
Dataset / Evaluation
这是一篇理论 lower-bound 论文，实验不是证据主体。数值部分只是在 random support function hard family 上展示三个现象：optimum 的 -k^{-1/2} 尺度、eps^{-2} 到 d 的 transition、以及 two-point method 相对 first-order baseline 的 d 维度代价。
这些实验基本支持 hard family 的几何直觉，但不验证 theorem，因为 theorem 已由证明给出。它们也不构成跨场景 evaluation：没有真实黑盒任务，没有多类函数族，没有实际 deployment。Coord-FD ACCPM 的高精度 saturation 只是与 O~(d^2) upper-bound landscape 一致，不能说明该算法在一般 nonsmooth convex objective 上达到最优。
因此 evaluation 的角色应理解为 sanity check / illustration，而不是 empirical claim。文中没有试图用实验证明 worst-case lower bound，这一点是合理的。
Limitation
第一，log gap 未解决。lower bound 是 dk/log k，而 upper bound 多项式尺度是 dk 或 d^2 up to polylog；文中未充分说明 log k 是否来自 proof looseness、one-step bound 的真实极值代价，还是 hard family 的限制。
第二，结论依赖 nonsmooth Lipschitz convex class。support function hard family 本质上利用 max nonsmoothness；对 smooth convex、strongly convex 或 PL/nonconvex stationarity，posterior energy 方法是否还能保留同样尺度并不直接成立。
第三，hard family 需要 k <= c d，并通过 k≈min{d,eps^{-2}} 产生 transition。这个构造很好地匹配当前 upper-bound landscape，但也意味着下界几何强绑定在“多个随机 linear pieces 的 aggregate direction”上。其他 oracle models 或更结构化函数族中，scalar value 可能暴露的信息结构不同。
第四，augmentation 暴露 active index 是分析上有利的 stronger transcript。它让 lower bound 更强，因为即使给更多信息仍然困难；但也可能遮蔽 value-only posterior 中更精细的结构。当前证明没有说明直接 value-only posterior 能否得到更紧的能量界。
第五，这不是关于实际 derivative-free optimization workload 的结论。真实目标往往有低维结构、smoothness、重复 query noise、模型结构或可利用先验；worst-case nonsmooth convex 下界不能直接外推到 LLM zeroth-order fine-tuning 等应用。
Takeaway
- 1. exact scalar value oracle 的维度代价不是 stochastic noise artifact；即使 noiseless、adaptive、精确实数反馈，nonsmooth convex worst-case 仍需要接近 d min{d,eps^{-2}} 次 evaluations。
- 2. 对 noiseless oracle lower bound，更有前途的度量不是 transcript KL，而是 posterior 中“任务相关 latent”的可用能量。
- 这里的 latent 是 aggregate direction；类似思路可迁移到其他 exact-feedback lower bounds。
- 3. active-index augmentation 是一个值得记住的 proof trick：给算法更多可分析信息，换取 posterior product structure，再证明即便如此仍学不够。
一句话总结
这篇论文把 exact zeroth-order convex optimization 的下界从粗糙的 local-oracle baseline 推到近最优尺度，核心贡献是一套用 posterior mean energy 控制 noiseless adaptive scalar observations 的 lower-bound 方法。