精读笔记
Problem Setting
论文标题：High-Probability Guarantees for Random Zeroth-Order Gradient Descent on Smooth Functions（arXiv preprint / 2026）。
这篇论文实际处理的是 deterministic smooth zeroth-order optimization 中一个长期被 expectation analysis 掩盖的问题：经典两点 Gaussian finite-difference ZO-GD 的单次运行能否有非粗糙的 high-probability 保证。这里算法本身并不新颖，难点也不是 estimator unbiasedness，而是 adaptive random trajectory 上的几何下降是否能稳定累计。
关键矛盾是：每一步只有一个随机方向，下降量取决于该方向在当前梯度方向上的平方投影 ζ_t。单步 ζ_t 可以几乎为 0，所以不存在有用的 per-step high-probability descent；但 expectation 分析只用 Eζ_t=1/d，无法说明单次轨迹。以前方法卡在这里后通常用 Markov 把 expectation bound 转成 high probability，代价是把 ε 改成 δε，造成 query 或 smoothing radius 的虚假 δ 依赖。
Motivation
作者反对的是 black-box Markov conversion，而不是现有 ZO 方法的平均复杂度。对于 deterministic objective，随机性完全来自算法采样方向；这种随机性具有可分析的几何结构，不应被当成任意非负随机变量用 Markov 处理。
核心缺口是：需要一个直接作用于自适应轨迹的概率分析，既能证明“很多步之后随机方向总会给足够多有效投影”，又能证明 finite-difference smoothing bias 沿路径不会累计过大。作者的观察是 normalized step size 可以把 Gaussian 长度和方向分开，方向部分变成 Beta projection martingale，长度部分变成 chi-square accumulation。这给了直接 high-probability proof 的入口。
Core Idea
真正的核心思想是把随机 zeroth-order descent 从“随机梯度估计器的矩控制”改写成“随机方向几何投影的累计控制”。用 η_t=1/(4L||u_t||^2) 后，下降项不再含有 Gaussian norm 的大幅波动，而是变成 ζ_t||∇f(x_t)||^2，其中 ζ_t 是单位随机方向对当前梯度方向的平方投影。条件于历史，当前梯度方向是固定的，所以 ζ_t 是 Beta-type 随机变量，均值 1/d，且可以通过 martingale lower-tail 控制其累计和。
这和 Nesterov-Spokoiny 式 Gaussian smoothing expectation analysis 的本质区别在于：本文不先优化 smoothed objective，也不通过 smoothed gradient 与 true gradient 的转换来承担高阶 Gaussian moment 代价，而是直接在原函数下降不等式里保留 finite-difference remainder。方向随机性负责下降，norm 随机性负责误差上界，二者被分开处理。这是本文最有迁移价值的建模变化。
Method
1. Two-point estimator 的 pathwise decomposition：把 g(x) 写成 uu^T∇f(x)+βu。它解决的是 finite difference estimator 在单条轨迹上不是精确 directional gradient 的问题；β 项由 smoothness 控制，最终转化为 Lα^2||u||^2 级别的累计误差。
2. Normalized stepsize η_t=1/(4L||u_t||^2)：它不是为了调参方便，而是为了把下降项中的 ||u_t||^2 归一掉。核心变化是下降几何只剩方向投影 ζ_t，而 Gaussian norm 的 heavy-tail 只进入 smoothing-error accumulation。
3. Projection lower-tail：单步 ζ_t 无法高概率下界，因此证明累计和 ∑ζ_t 或 weighted sum ∑w_tζ_t 的下界。强凸用 unweighted / suffix lower bound 处理线性收缩和历史误差折扣；非凸用 weighted lower bound 处理 w_t=||∇f(x_t)||^2。
4. Smoothing-error upper-tail：用 chi-square tail 控制 ∑||u_t||^2，从而控制 ∑Δ_{α,t}。这一步决定了 α 的 pathwise 条件，也是本文 high-probability guarantee 的主要代价来源。
5. 不同函数类的闭合方式：强凸用 PL-type gradient-growth 得到乘法收缩；凸情形用 level-set radius R 把 gap 转成 gradient lower bound；非凸情形先由 lower boundedness + smoothness 推出路径上的梯度上界，再使用 weighted martingale。
Key Insight / Why It Works
最核心贡献是识别出 normalized Gaussian direction 的 Beta projection 是可以沿 adaptive trajectory 做 lower-tail 控制的。这里 adaptive 并没有破坏分布结构，因为 x_t 和 ∇f(x_t) 对 u_t 之前的历史可测，而 u_t 独立；因此条件分布仍然是固定方向下的 Gaussian projection。这一点是整篇证明成立的支点。
第二个关键点是把 finite-difference bias 当作路径扰动，而不是 smoothed objective bias。NS 路线里，非凸 stationarity 要从 smoothed gradient 转回 true gradient，会付出 d^3 Gaussian moment 因子；本文直接对 original f 的下降式做误差控制，因此非凸 α 的维度尺度可从 d^{-3/2} 改到常置信度下的 d^{-1}。这个增益不是 scaling，也不是工程 trick，而是 proof object 改变带来的。
不过，凸情形的代价也暴露得很清楚：pathwise smoothing error A_{α,T}≈Lα^2 dT 必须小于 ε，而 T≈dLR^2/ε，于是 α 变成 O(ε/(dLR))。这比 expectation analysis 的 O(√ε) 更严格。换言之，本文用更小 finite-difference radius 换取 fixed-confidence query complexity 中去掉 Markov 的 1/δ。这个 trade-off 是实质的，不应被解读成全面支配 prior。
强凸结果最漂亮：query 的 confidence cost 是 additive log(1/δ)，且 leading α scale 不被 √δ 压小。但强凸 smoothing cap 中仍有 log terms 和 dL/µ 项，说明 high-probability smoothing error 与 contraction tail 的耦合没有完全消失。部分常数和 loglogT 明显像 proof artifact。
这篇论文的有效性不来自 data、retrieval、representation alignment 或 scaling；它是一个概率分析重构。最可能可迁移的 insight 是：对于随机搜索 / sketching 类算法，不要直接对 estimator 做全局范数 concentration，而应寻找能把“有用随机性”和“有害随机性”分离的 normalization，使 descent variable 进入可累计的低维几何分布。
Relation To Prior Work
最接近的是 Nesterov and Spokoiny 的 Gaussian smoothing random gradient-free framework。NS 的主线是 expectation：利用随机估计器的均值和二阶矩给出平均收敛，再通过 smoothing bias 连接到原函数。本文保留两点 Gaussian estimator，但完全换了分析对象：不是 smoothed objective 的 expected descent，而是 original objective 上的 realized trajectory descent。
和 Markov-converted NS 相比，本文真正新增的信息是 confidence dependence 的结构：δ 不必乘进 ε；强凸和凸 query complexity 中 confidence overhead 可以是 additive log(1/δ)，非凸是 d+log(1/δ)。这不是简单常数改善，而是说明算法内部随机性有可累积几何规律。
和 multi-point high-probability ZO / randomized sketching 方法相比，本文更保守也更干净：不通过每步多查询制造 per-step good direction，而是坚持 two-query 并承认单步可能失败，只证明长期累计成功。因此它属于“randomized coordinate/descent martingale analysis”谱系，而不是 model-based DFO 或 trust-region 谱系。
看似新的 algorithmic ingredient 其实只有 normalized stepsize；two-point estimator 本身是经典的。实质创新在分析方式：Beta projection lower-tail + Gaussian norm upper-tail 的分离，以及在非凸情形避免 smoothed-gradient conversion。
Dataset / Evaluation
没有 dataset，也没有 empirical evaluation。这对本文不是致命问题，因为 claim 是理论保证而非实际性能；但也意味着论文没有证明 normalized stepsize 在真实 black-box optimization 中比 fixed O(1/(dL)) stepsize 更稳定或更快。
理论 evaluation 覆盖三类标准 setting：strongly convex、convex、lower-bounded non-convex。覆盖面足够支撑“direct high-probability analysis is possible”这个 claim。但它没有覆盖 noisy oracle、constrained domain、nonsmooth objective、stochastic simulation 这些真实 zeroth-order deployment 中更常见的场景。
因此，结果验证的是概率分析路线，而不是算法工程优势。若读者关心实际 DFO performance，这篇论文提供的是理论机制，不是 benchmark evidence。
Limitation
1. Deterministic oracle 假设很强。真实 zeroth-order 场景常有函数值噪声，two-point difference 会放大噪声；当前 proof 只控制 smoothness remainder，不控制 observation noise。扩展到 stochastic oracle 不是直接加一项那么简单。
2. 需要 L 并使用 η_t=1/(4L||u_t||^2)。理论上 ||u_t||>0 a.s.，但数值上小 norm 会导致大步长；文中未充分说明实际实现中是否需要 clipping，以及 clipping 是否破坏证明。
3. Convex guarantee 依赖 R_ε 或 R_{α,T}(δ)。这不是普通初始距离，而是 enlarged level set 到解集的最大距离；它可能隐藏了目标函数全局几何条件。对 flat valley 或非紧 level set 问题，保证可能退化。
4. α 条件是主要上限。尤其 convex high-accuracy regime 中 α=O(ε/(dLR))，这可能比 expectation-based radius 更苛刻，实际 finite-difference 会更容易受数值精度或 oracle noise 影响。
5. 常数非常大，suffix bound 中 501、250、1000 等常数显然不是 tight。loglogT 也很可能是 dyadic union bound artifact。理论结构可信，但 finite-sample 常数不适合作实际 guideline。
6. 输出形式仍有限制：非凸是 trajectory average / min iterate stationarity 证书，不是 last iterate；而且算法本身没有提供如何在 zeroth-order setting 中识别 min-gradient iterate 的额外机制。
Takeaway
- 1. 对 randomized ZO 方法，高概率分析的关键不是让每步方向都好，而是证明很多坏方向不会阻止累计投影达到 1/d 量级；这是比 Markov conversion 更正确的概率对象。
- 2. Normalization 可以改变可证明性。
- η_t∝1/||u_t||^2 把 Gaussian norm 从 descent 中剥离出来，使方向几何变成 Beta martingale；这类“先分离随机源再 concentration”的技巧值得迁移到 sketching、random subspace、coordinate-free descent 分析。
- 3. Direct pathwise proof 的收益和代价都很明确：query confidence dependence 更好，但 smoothing radius 可能更小，尤其凸问题中 α 的 ε 依赖变差。
一句话总结
这篇论文在经典 two-query Gaussian ZO-GD 上通过 normalized stepsize 和自适应 Beta 投影 martingale 分析，把 expectation-era 的随机梯度估计器理论推进到 direct finite-horizon high-probability 轨迹理论。