精读笔记

Problem Setting

《High-Probability Last-Iterate Guarantees for Two-Point Gaussian Zeroth-Order Stochastic Gradient Descent》（arXiv preprint / 2026-06-19）研究的是 smooth strongly convex stochastic zeroth-order optimization 中标准 two-point Gaussian SGD 的单次运行终点保证。这里的核心问题不是能否用 two-point estimator 得到 O(d/T) 的期望收敛，这已经是经典事实；真正问题是 last iterate 是否能在 high probability 下保留同一 zeroth-order scale，并且只付 log(1/δ) 而不是 1/δ。

困难点有两个。第一，随机方向的 descent term 是 (u_t^T∇f(x_t))²，路径上不能逐步下界，因为 angle ratio 有 χ²/Beta 型 lower tail；所以不存在 per-step deterministic contraction。第二，随机有限差分误差在递推展开后会被未来 contraction product 加权，形成 signed adaptive suffix-product term；如果直接取绝对值或用 deterministic envelope，会丢掉 cancellation，rate 很容易变松。以前方法主要卡在 expectation analysis、Markov conversion、bounded/clipped noise 或 averaged/regret criterion，不能直接回答“标准 recursion 的部署终点是否可靠”。

Motivation

已有路线缺的是 last-iterate 的直接 concentration，而不是又一个 zeroth-order 期望界。Markov 从 E[f(x_T)-f*]≤O(d/T) 得到的 confidence bound 会变成 O(d/(δT))，这在单次运行部署场景里基本不是正确的 tail 行为；它只是一个 generic conversion artifact。另一方面，robust/clipped 方法虽然能做 high probability，但改变了算法，回答的是另一个 procedure。

作者的核心观察是：标准 same-sample Gaussian recursion 里其实有两类可利用的路径结构。随机角度虽然每步可能很差，但按 1/(t+T0) 加权后在所有 suffix 上有 aggregate contraction；线性噪声虽然被未来随机 product 加权，但它是 signed martingale，不应在 concentration 前被绝对值化。论文的动机就是证明：只要分析不破坏这两类结构，标准算法本身可以达到接近 expectation rate 的 high-probability last-iterate 保证。

Core Idea

核心思想是把 zeroth-order SGD 的路径分析从“局部一步下降”改成“全局 suffix 权重扫描”。随机方向带来的下降不是每一步稳定发生，而是在任意 relevant suffix 上以足够概率累计发生；weighted scan 正是把 Beta angle 的平均 1/d 行为转成路径级 contraction envelope。这个转变很关键，因为它避开了对 ζ_t 做 uniform lower bound 的不可能性。

第二个核心是保留线性噪声项的符号与真实 suffix product。递推展开后，time k 的噪声项乘上未来方向决定的 Π_{K,k}；如果先用 |Π| 或 ρ envelope 粗暴上界，会把 martingale cancellation 抹掉。作者通过 angle-enlarged filtration 先“揭示”未来角度但不改变当前噪声条件分布，再用 stitched product-martingale boundary 控制 signed sum。与 prior 的本质区别不是 estimator 变了，而是信息流被重新组织：未来 contraction 被纳入 martingale variance geometry，而不是被当作外部 deterministic worst-case weight。

Method

方法层面可以压缩成四个必要机制。

1. Norm-normalized stepsize：η_t=4d/[μ(t+T0)||u_t||²] 的作用不是 tuning trick，而是让 η_t||u_t||² deterministic，使主递推的 contraction factor 变成 1−2dζ_t/T_t。这样方向 norm 的随机性不再污染主下降项，只剩 angle ζ_t 需要处理。

2. Weighted scan for Gaussian angles：它解决的是“每步 angle 可能极小”的不可控性。通过对所有 intervals/suffixes 做加权 lower scan，证明累计 ∑ζ_t/T_t 接近其均值尺度，从而给 suffix product ρ_{K,k} 提供路径级 envelope。核心变化是从 pointwise contraction 到 aggregate contraction。

3. Angle-enlarged product martingale：它解决 signed linear stochastic error。未来角度决定 product weight，但由于 Gaussian rotational invariance，未来 angle 的条件 law 不依赖当前 oracle noise；因此可以扩大 filtration，同时保持 e_k 的 conditional sub-Gaussian projection bound。这个步骤是证明中最有辨识度的机制。

4. Terminal nonnegative controls：quadratic-noise 和 smoothing-bias 项是非负项，不需要像线性项那样保留 cancellation。论文只在 terminal T 上做 raw projection、quadratic noise、smoothing bias 控制，再通过 deterministic terminal comparison 转回任意 K，避免对所有 K 直接 union bound。这部分更像必要的 bookkeeping，但它对维持 logarithmic confidence cost 也重要。

Key Insight / Why It Works

这篇论文真正有效的原因是它没有把 zeroth-order 随机方向当成每步近似梯度，而是把它当成一个可扫描的随机投影过程。单步投影的 lower tail 很差，但加权 suffix 累计有稳定质量；这正好匹配 strongly convex SGD 的 1/t schedule。因此，下降机制不是“每一步都好”，而是“任何足够长的未来 suffix 总体够好”。这是本文最可迁移的 insight。

第二个关键 insight 是：last-iterate recursion 中最危险的不是二次噪声，而是 signed linear term 的 product-weighted structure。传统 conservative 分析会在这里取绝对值，导致方差 proxy 膨胀；本文保留 Π_{K,k} 直到 martingale concentration 完成，等 cancellation 被用完后才用 deterministic envelope 控制 variance。这是 rate sharpness 的主要来源。

相比之下，same-sample two-point estimator、α=1/sqrt(d(T+T0))、T0=Θ(dL/μ) 等更多是使标准 zeroth-order bias/variance 与 stability 对齐的工程化参数选择。它们必要，但不是概念突破。论文的本质贡献不是 scaling、data coverage、retrieval、test-time compute 或 representation alignment，而是一个针对 stochastic approximation recursion 的 pathwise concentration decomposition。

需要注意，结果的 O~(d/T) 并不说明算法在所有黑盒场景都“实际稳健”；它说明在相当理想的 oracle/noise/convexity 条件下，标准 recursion 的 tail 行为可以被更紧地证明。这里没有 hidden benchmark issue，因为没有实验 benchmark；但也因此不能把理论 claim 外推到非凸高维模型适配或 LLM fine-tuning。

Relation To Prior Work

最近的参照系有三类。第一类是 classical zeroth-order expectation results，如 Ghadimi-Lan、Nesterov-Spokoiny、Duchi-Shamir、Wang 等，它们给 O(d/T) 或相关 minimax/expected guarantees，但不回答 single-run last iterate high probability。本文是在同一 zeroth-order rate scale 上补 confidence/last-iterate 维度。

第二类是 first-order high-probability last-iterate SGD，尤其 Liu & Zhou 2023。本文明显借鉴其 conditional sub-Gaussian noise 与 last-iterate induction 风格，但 zeroth-order 额外引入 Gaussian angle scan、finite-difference bias、random product weights。这不是简单把 first-order proof 乘一个 d，而是处理了随机方向导致的 missing per-step contraction。

第三类是 robust/clipped/high-probability zeroth-order 或 bandit regret。那些结果通常改变算法、输出平均/ regret、依赖 boundedness 或 clipping。本文的实质新增信息是：对 unmodified same-sample Gaussian SA recursion，可以直接证明 logarithmic-confidence last-iterate bound。看似新的算法成分其实很少，真正创新集中在 proof architecture：weighted suffix scan + angle-enlarged product martingale。

Dataset / Evaluation

没有 dataset / empirical evaluation；这是纯理论论文。评价证据是定理、推论和证明，而不是 benchmark。

从 claim 支撑角度看，理论评价是匹配的：论文声称的是 smooth strongly convex stochastic optimization 下标准 same-sample two-point Gaussian recursion 的 high-probability last-iterate guarantee，证明正是针对这个对象。它没有验证真实 black-box simulation、bandit learning、MeZO/LLM adaptation 或非凸训练；文中这些例子只是 motivation，不应被理解为 empirical support。

因此 evaluation 的 limitation 很清楚：它只验证了一个数学 recursion 在一组强假设下的 finite-horizon tail bound。它不能说明实际 zeroth-order training 中 oracle noise 满足 full-vector conditional exponential moment，也不能说明 same-sample common-random-numbers oracle 总是可得，更不能说明在非凸模型中 last iterate 有类似行为。

Limitation

最重要的限制是 dimension-horizon-confidence compatibility：d ≥ 16 log(6T/δ)。这不是无害条件；固定 d 和 δ 时，T 不能任意增大，作者在 remark 中也承认 oracle-complexity corollary 只对 admissible horizon 成立，不是 fixed-d 下 ε→0 的无条件结论。这个条件来自 Gaussian norm event 和 product-weight polynomial envelope，是 proof 的结构性成本。

第二，noise assumption 很强。Assumption 3 是 full-vector squared norm 的 conditional exponential moment bound，比 coordinatewise sub-Gaussian 或 bounded variance 强得多；如果 σ 本身随 d 增长，所谓 O~(d/T) 中隐藏的维度依赖会重新出现。论文把 σ 作为 fixed problem parameter，这在理论表述上合理，但在高维应用中可能掩盖主要成本。

第三，same-sample two-point oracle 是关键前提。它利用 common random numbers 消掉 independent differencing noise，使随机误差可写成 gradient noise projection；如果两次 function evaluation 用独立样本，噪声结构会显著不同，本文机制未直接覆盖。

第四，算法需要 horizon-dependent α，并依赖 L、μ 设置 T0 和 stepsize；这不是 fully adaptive procedure。最后，结果只在 smooth strongly convex 下成立，和论文动机中提到的高维模型适配、LLM forward-only tuning 之间存在明显 deployment gap。这里的“泛化”主要是 proof technique 的泛化潜力，不是算法在真实任务上的泛化能力。

Takeaway

• 1. 最值得记住的是 proof viewpoint：zeroth-order SGD 的 high-probability last-iterate 分析不应强求 per-step angle lower bound，而应控制所有 suffix 的 weighted aggregate alignment。
• 2. Product-weighted linear noise 是 last-iterate analysis 的核心障碍；保留 signed suffix product 直到 martingale concentration 之后，可能是很多 stochastic recursion 中避免松界的通用技巧。
• 3. 这篇论文真正推动的是“标准算法的精细 tail analysis”，不是提出更强 optimizer。
• 后续更有价值的问题是把这种路径级 scan/martingale machinery 推到 weaker noise、independent samples、adaptive stepsizes、nonconvex geometry 或 momentum/variance-reduced zeroth-order methods。

一句话总结

这篇论文在 zeroth-order stochastic approximation 谱系中不是算法创新，而是一次精细的路径级 concentration 推进：它证明标准 same-sample two-point Gaussian SGD 在强凸、sub-Gaussian gradient-noise 条件下可以直接获得 logarithmic-confidence 的 O~(d/T) last-iterate 保证。