精读笔记
Problem Setting
《Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity》（arXiv preprint / 2026）关注的是可调精度零阶 oracle 下的真实时间复杂度，而不是传统 oracle-call complexity。问题的实质是：每次函数值查询可以通过更高计算预算得到更小误差 δ，但代价 c(δ) 随 δ 变小而上升；算法必须联合选择迭代数 N、每步 fidelity schedule {δ_k}、batch size B、平滑半径 h 和优化模板。
真正困难点在于误差不是单一噪声常数。零阶方法里 oracle noise 会先通过 finite-difference / kernel estimator 转成 gradient bias 和 variance，再被 GD/FGM/SGD 的动力学放大或衰减。已有 ZO 理论通常只问“给定 δ 收敛到什么精度”或“给定 ε 需要多少 oracle calls”，但没有把 δ 的计算成本放进优化问题。因此它无法回答一个实际 deployment 问题：是少量高精度查询更快，还是大量低精度查询更快？
关键矛盾是 fidelity 与 iteration/batching 之间的替代关系。高 fidelity 降低 bias/variance，但每次查询贵；低 fidelity 便宜，但需要更多迭代、batching 或更保守的算法模板。论文的贡献在于把这个矛盾形式化，并展示 cost exponent γ 会改变“最优算法”本身。
Motivation
已有路线的问题不是没有 ZO 收敛界，而是这些界没有被解释成资源分配规则。在 simulation-based optimization、MCMC PageRank、Monte Carlo physics 等场景中，oracle 精度本来就是可调 knob；把它当固定噪声水平等于忽略了最主要的系统成本。
作者的核心观察是：许多 ZO 收敛界虽然表面不同，但 fidelity 进入误差的方式常常可以拆成 ∑α_kδ_k^p 这样的通道。只要这一结构成立，最优 fidelity schedule 就不需要重新分析算法，而可以从已有 convergence bound 中直接读出。缺口就是缺少一个“从理论收敛率到 wall-clock-optimal tuning”的编译层。
另一个动机是纠正 acceleration 的默认偏好。传统 complexity 里 FGM 因为迭代数少通常更好，但在 inexact oracle 下 acceleration 可能对误差更敏感，迫使使用更高 fidelity；如果 fidelity 昂贵，加速可能在 wall-clock 下输给 GM。这是本文最有价值的反直觉出发点。
Core Idea
论文真正核心不是一个新 estimator，而是一个建模与归约：把 tunable-fidelity ZO 写成 constrained wall-clock optimization。给定误差界 Gap_N≤E_0(N)+∑α_kδ_k^p 和 cost c(δ)=δ^{-γ}，固定 N 下最优 δ_k 有闭式形式 δ_k∝α_k^{-1/(p+γ)}。也就是说，误差传播系数 α_k 大的迭代应该用更高 fidelity，α_k 小的位置可以粗糙查询。这个结论把 fidelity schedule 从 heuristic tuning 变成了误差通道上的资源分配。
与 prior 的本质差异在于评价对象变了。传统 ZO 关注如何减少调用次数或改善 estimator variance；本文关注在 oracle 精度可购买时，哪个组合的总购买成本最低。它引入的 inductive bias 是“精度应按误差传播权重分配”，而不是均匀地把所有 oracle calls 做到同样准。这个 bias 对任意满足 separability 的算法都可迁移。
理论上它成立的原因很直接：power-law cost 与 power-law error channel 形成可解析的弹性权衡，γ 控制“买精度”相对于“多调用”的边际价格。不同 noise model 下 δ 进入 bias/variance 的方式不同，所以 γ 的角色也不同：adversarial noise 中主要影响算法模板选择；Tsybakov noise 中主要影响 batching/fidelity 的替代边界。
Method
1. Wall-clock model：每次查询以 fidelity δ 运行，成本为 δ^{-γ}，总时间为 ∑c(δ_k)。它解决的是传统 query complexity 与真实运行时间脱节的问题。核心变化是把 δ 从 analysis nuisance parameter 变成 optimization variable。
2. Fidelity-separable bound：要求误差可写为 E_0(N,Θ)+∑α_k(N,Θ)δ_k^p。它的作用是把 algorithm dynamics 与 oracle fidelity 解耦。E_0 表示无噪声/基准收敛，α_k 表示第 k 次 oracle error 对最终 gap 的传播权重，p 表示该误差通道的幂次。
3. Master allocation lemma：固定 N 时最小化 ∑δ_k^{-γ} subject to ∑α_kδ_k^p≤ε。解给出 δ_k^* 和 T_total(N) 的闭式表达。它带来的核心变化是：任何已有收敛界只要能转成 separable form，就能自动生成 fidelity recommendation。
4. Uniform vs adaptive schedule 判断：论文没有盲目鼓吹 adaptive fidelity，而是用 Jensen gap Δ=p+σγ−ρ(p+γ) 判断非均匀 schedule 是否有多项式收益。结论很克制：若 α_k 只是温和变化，如 j^{-a}，非均匀 schedule 通常只有常数收益；只有 heavy-tailed 或 spike-like α_k 才有真正 asymptotic speedup。
5. Bias/variance interface：通过 b_k 和 V_k 把 ZO estimator 的 fidelity dependence 注入到一阶优化模板。kernel two-point estimator 下，bias 有 Lh^{β−1}+dδ/h，second moment 有 d^2δ^2/h^2。这个接口是方法泛化到不同 estimator/noise model 的关键。
6. Case studies：adversarial noise、Tsybakov noise、PageRank MCMC oracle 不是独立模块，而是用来展示同一 master lemma 如何产生不同相变。adversarial 部分强调 γ=1 的 GM/FGM 选择；Tsybakov 部分强调 γ=2 的 fidelity-vs-batching threshold。
Key Insight / Why It Works
最重要 insight 是：在 tunable oracle 下，算法优劣不能只看迭代复杂度，而要看“迭代减少”是否值得“更高 fidelity 成本”。Acceleration 的收益是减少 N，但它可能改变 α_k 的形状或放大噪声通道；当 γ 大时，买足够精度来支撑 accelerated dynamics 太贵，所以 GM 可能 wall-clock 更优。这不是 implementation artifact，而是 cost exponent 与 error propagation 的结构性冲突。
第二个 insight 是 γ 的语义依赖 noise model。adversarial noise 主要形成 bias-like floor，γ 决定使用哪种 optimization template；Tsybakov noise 是 variance-like，可通过 batching 平均，因此 γ 决定“降低 δ”还是“增加 B”。γ=2 阈值很自然：若 variance ∝δ^2，而 cost ∝δ^{-γ}，当 γ=2 时单位 variance reduction 的成本近似持平；γ>2 时高 fidelity 过贵，overbatching 更合理。
第三个 insight 是 adaptive fidelity 的收益通常被高估。master lemma 看起来支持逐步调 δ_k，但论文的 Jensen gap 分析说明：除非 α_k 非常集中，非均匀 schedule 相对 uniform schedule 只有常数或对数级收益。这是一个有价值的负结论。它暗示工程上大量场景用 constant fidelity 已足够，真正要优化的是模板选择、batching 和边界 fidelity，而不是精细 per-iteration schedule。
最核心贡献是抽象层面的“convergence-bound compiler”。IGM、PageRank demo、具体常数推导都更像支撑材料。可能只是辅助甚至 engineering 的部分包括：PageRank 实验的 proxy Gaussian oracle、深度学习 γ 估计、部分 phase transition 数值验证。这些实验没有提供强泛化证据，但足以说明理论机制不是纯符号游戏。
这篇不是 scaling paper，也不是 data coverage 带来的收益；它的价值来自更合适的成本模型和资源分配 inductive bias。若要迁移，关键是先把目标方法的误差界拆成 fidelity channels，再看 γ 与通道指数如何决定 resource allocation。
Relation To Prior Work
最接近的是 inexact oracle / tunable oracle 优化理论，尤其 Van Dessel & Glineur 关于一阶 convex optimization 的 optimal inexactness schedules。本文的实质扩展在于 ZO 场景里 fidelity 不只影响 gradient error，还直接影响函数值差分估计，进而通过 h、B、bias/variance 多通道耦合进入收敛界。
和传统 ZO work 的区别不是 estimator 更强。kernel two-point、finite difference、accelerated ZO-SGD、Akhavan/Tsybakov 高阶平滑分析等基本都是已有组件；本文把它们重新组织到 wall-clock fidelity allocation 框架里。看似新的很多公式，本质是已有收敛率加上 power-law oracle cost 后的解析优化。
IGM 是相对实质的技术补丁：为了在 adversarial time-varying inexactness 下得到可用的 α_k 结构，作者构造了介于 GM 与 FGM 的方法并证明收敛。它不是主线创新，但使 γ=1 template selection 的论证更完整。
在技术谱系上，这篇属于 optimization complexity 的 cost-aware / oracle-aware 分支，而不是 black-box optimization heuristics。它推动的是复杂度度量的升级：从“调用多少次 oracle”到“以什么 fidelity 调用 oracle 才最省时间”。
Dataset / Evaluation
实验覆盖了三类 claim：GM vs FGM 的 γ 相变、adaptive vs uniform fidelity schedule、PageRank/MCMC oracle 下 γ=2 batching threshold。整体上实验是机制验证，不是广泛 benchmark。
PageRank 部分是最贴近实际 oracle-cost motivation 的案例，因为 MCMC stationary distribution estimator 自然给出 c(δ)≈δ^{-2}。但主实验大量使用 calibrated Tsybakov Gaussian proxy，而不是端到端真实 MCMC oracle；真实 sampler 主要用于验证 δ^{-2} scaling。严格说，它验证的是理论模型在合成 PageRank-like 实例上的定性行为，而不是复杂真实 PageRank 学习系统的 deployment performance。
GM/FGM 比较和 scheduling 实验支持相变方向，但维度、问题类型和目标精度都有限。实验没有充分覆盖不同 γ 的真实来源、non-polynomial cost、switching overhead、并行调度开销，也没有展示在大型 expensive simulator 上的 wall-clock 实测。因此 evaluation 支持“理论机制可观察”，但不足以证明“实际 BBO 系统中闭式 recipe 直接最优”。
文中一些 deep learning γ 估计更像 appendix motivation，增益来源不清，且 FP16/FP64 loss discrepancy 与 tunable black-box oracle fidelity 并不完全同构。
Limitation
1. Power-law cost 是核心但也是脆弱前提。真实 oracle 可能有 fixed overhead、warm-start、缓存、离散精度级别、并行吞吐瓶颈或 regime-dependent γ。若 c(δ) 不是稳定 power-law，γ phase transition 可能只是局部现象。
2. Fidelity switching cost 被忽略。Prop. 1 默认每步可无成本改变 δ_k；实际 Monte Carlo simulator、inner PDE solver、物理实验或 MCMC pipeline 都可能有重配置成本。这样最优逐步 schedule 可能不可部署，piecewise-constant policy 才合理。
3. High-precision asymptotic 依赖强。很多结论是 ε→0 下的 leading-order scaling；moderate ε 时边界 δ=1、batch upper/lower constraints、平滑半径约束会主导，实验中 phase transition 偏移已经说明这一点。
4. 常数已知假设很强。最优 N,B,δ,h 依赖 L,μ,β,σ_*,κ 等；实际若这些未知，需要额外估计或 adaptive control。论文没有充分解决 online tuning 问题。
5. Fidelity-separability 不是普适 BBO 结构。它适合许多 first-order-template ZO 方法，但对 Bayesian optimization、trust-region、surrogate-assisted optimization、多保真模型学习等场景，误差不是简单通过 α_kδ_k^p 累积。文中未充分说明这些方法能否纳入。
6. 实验偏合成。PageRank demo 有现实动机但规模小，proxy oracle 简化明显；真实 deployment 中 wall-clock 受并行硬件、采样相关性、communication、inner solver convergence 影响。benchmark 不能完全支撑工程最优 claim。
7. 一些收益可能只是 scaling interpretation，而非新算法性能。本文主要告诉你如何重新计账；如果已有算法的 convergence bound 很松，那么编译出的 fidelity recipe 也会继承松界。
Takeaway
- 1. 对 tunable-fidelity ZO，不应默认优化 oracle calls；必须优化 fidelity-adjusted wall-clock。
- 否则 acceleration、batching、精度选择的结论都可能反。
- 2. 最可迁移的工具是 fidelity-separable decomposition。
- 以后分析任何 ZO 方法时，都应显式报告 α_k、p、E_0，而不是只给 uniform δ 的收敛界。
一句话总结
这篇论文把零阶优化从 query-complexity 分析推进到 tunable-oracle 的 wall-clock 资源分配框架，核心贡献是用 fidelity-separable bound 将已有收敛理论编译成最优精度、batching 与算法模板选择规则。