精读笔记

Problem Setting

论文标题：Non-convergence Analysis of Probabilistic Direct Search（arXiv preprint / 2026）。

这篇论文实际解决的问题是：PDS 的 probabilistic descent 条件是否只是为了证明方便，还是典型随机 direct search 全局收敛的必要结构。这里的“非收敛”不是发散，而是 iterates 不能渐近达到 stationarity；更强地，作者证明在某些条件下轨迹会以正概率收敛到初始点附近的非平稳区域。

真正困难点不在于构造一个坏例子，而在于建立一个参数阈值级别的系统性理论：当每轮随机方向数 m 不足时，算法不是偶然失败，而是由步长乘法过程和方向覆盖概率共同导致的结构性失败。以前的 convergence theory 只给出 sufficient condition：若方向集以概率 p0 覆盖下降半空间，则 liminf ||∇f||=0 a.s.；但它不能回答 p0 以下发生什么。

关键矛盾是 per-iteration cheapness 与 global coverage 之间的冲突。PDS 用少量随机方向替代 deterministic positive spanning set，降低单轮成本；但如果随机方向集太稀疏，它会频繁完全落在非下降半球，导致步长持续收缩并把算法锁死在起点附近。本文证明这个矛盾不是分析松弛，而是算法机制本身。

Motivation

已有路线的问题是只从“成功概率足够高”推导收敛，而没有反向说明“成功概率不够高”是否真的危险。submartingale-like 假设在随机优化中已经成为模板：每步有足够概率出现 good model / descent direction / successful step，然后用随机过程工具证明某种 stationarity。这个模板的弱点是 necessity 不清楚。

作者的核心观察是：PDS 的步长更新是一个非常干净的乘法过程。成功时乘 γ，失败时乘 θ；如果失败事件和“没有下降方向”绑定，那么方向采样概率直接决定步长过程的长期指数漂移。一旦失败频率超过临界值，累计可移动距离会被压到有限甚至任意小，从而产生非收敛。

关键缺口在于：过去只有 convergence side 的阈值 m>log2(1-logθ/logγ)，没有 non-convergence side。本文想证明这条阈值几乎是 sharp 的，从而确认 probabilistic descent assumption 对典型 PDS 是 essential，而不是 proof artifact。

Core Idea

核心思想是把 PDS 的行为从几何下降分析改写成一个 0-1 随机过程驱动的随机级数问题。定义 Y_k=1 表示当前方向集包含某个下降方向，Y_k=0 表示整个方向集都不是下降方向。对凸函数而言，Y_k=0 是一个强事件：任何 polling direction 都不可能满足 sufficient decrease，因此 x_{k+1}=x_k 且 α_{k+1}=θα_k。于是 PDS 的复杂轨迹被压缩为两个级数：U_k 描述步长尺度，∑Y_k U_k 描述总位移。

这与 prior convergence analysis 的本质区别是方向相反：prior 证明 good events 足够频繁则 stationarity 被迫出现；本文证明 bad events 足够频繁则算法被迫局部化在起点附近。它引入的不是新的算法，而是新的 failure modeling：从“下降方向覆盖”转到“下降方向缺失”，再用乘法漂移阈值 p*=logγ/log(θ^{-1}γ) 刻画失败概率的临界点。

理论直觉很清楚：若 bad event 频率为 p，则 log U_k/k 近似 (1-p)logγ+p logθ。当 p>p* 时该量为负，步长尺度指数衰减；更强的是，conditional Chernoff bound 保证这种衰减不仅平均发生，而且以正概率足够早、足够强地发生，使总位移小到无法离开初始非平稳邻域。

Method

1. Probabilistic ascent：它解决的是如何形式化“随机方向集太差”。条件 P(cm(D_k,-G_k)≤0 | F_{k-1})≥p 表示在当前梯度非零时，方向集中没有任何下降方向的条件概率至少为 p。它是 probabilistic descent 的反面，但作者处理得比较细，加入 1(G_k≠0) 避免 cm(·,0) 定义影响理论。

2. 凸性桥接算法事件：probabilistic ascent 本身只是几何事件；要让它影响 iterate，需要凸性。若所有 d∈D_k 都满足 d^T∇f(X_k)≥0，则凸性保证沿这些方向函数不会下降，sufficient decrease 不可能成立。这一步是全文机制成立的关键前提，也是非凸无法直接推广的原因。

3. 随机级数控制轨迹：作者证明 sup_k ||X_k-x_0|| ≤ α_0∑Y_k U_k ≤ α_0∑U_k。这个不等式把非收敛问题变成级数小球概率问题：只要 ∑Y_k U_k 小于初始点到 stationarity set 的距离，轨迹就永远不可能达到 stationarity。

4. 从 Markov 到 conditional Chernoff：Markov inequality 给出一个粗糙非收敛条件 p>(γ-1)/(γ-θ)，但这不匹配收敛阈值。真正贡献是 conditional Chernoff bound，它控制 Y_k 的经验均值尾部，得到 sharp 临界 p>p*，并推出 P(∑Y_k U_k<ζ)>0 以及 ζ^{log p/logθ} 型下界。

5. 典型实现的阈值闭合：对 m 个独立均匀球面方向，完全落在非下降半球的概率为 2^{-m}。代入 p>p* 后得到 m<log2(1-logθ/logγ)，几乎正好补上既有收敛条件的反面。

Key Insight / Why It Works

最重要的 insight 是：PDS 的全局收敛并不只依赖“偶尔找到下降方向”，而依赖成功/失败事件与步长乘法过程之间的平均对数漂移。只要失败概率越过 p*，算法的可移动预算就会以正概率被提前消耗掉；后续即便偶尔成功，也没有足够步长逃离初始邻域。这是比“方向数不够所以覆盖差”更深的机制。

本文真正有效的部分不是 probabilistic ascent 这个定义本身，而是 Lemma 3.2 加 Proposition 3.3 的组合：前者把优化轨迹上界为随机级数，后者证明这个级数在 0 附近有正概率质量并给出幂律下界。这使得非收敛从例子变成了可量化理论。

哪些是辅助？Markov inequality 版本主要是 warm-up，条件更强且不 sharp。数值实验也只是辅助，不能承担主 claim。nonsmooth extension 是自然推广，技术上合理但不是核心增量；它主要说明机制依赖的是 directional derivative 的非负性，而非 classical gradient。

这不是 scaling，不是 data，不是 retrieval，也不是 hidden supervision；它是一个随机过程 / algorithmic dynamics 归因。若套用机器学习语言，真正的 inductive bias 是“bad event 的 multiplicative contraction 会形成吸收式局部化”。这类 insight 可以迁移到任何 success/failure 控制 trust-region radius、line-search step size 或 model accuracy radius 的随机算法。

一个直接判断：这篇论文最有价值的贡献是把 submartingale-like assumption 的 necessity 证明成了几乎 sharp 的 phase transition，而不是又给一个 non-convergence counterexample。它把 convergence theory 中看似保守的概率阈值反向验证了。

Relation To Prior Work

最接近的是 Gratton et al. 的 probabilistic direct search 收敛理论。prior work 的主线是：若 D_k 是 p0-probabilistic κ-descent set，则 PDS 全局收敛。本文不是改进 PDS，也不是给更好算法，而是证明当典型随机方向低于同一阈值时，PDS 对凸目标都可能非收敛。因此它是 convergence theorem 的 necessity companion。

与传统 direct search / GPS 非收敛工作相比，本质差异在于本文不是构造特定坏方向或坏函数，而是给出概率条件下的一般非收敛机制。Audet 对 GPS 的 tightness 是 deterministic condition 的 tightness；本文对应的是 randomized condition / submartingale-like assumption 的 tightness。

与 probabilistic trust region、probabilistic line search、probabilistic cubic regularization 等路线的关系更像方法论上的。那些工作依赖同类 P(F_k | history)≥P0 假设，但通常只证明 sufficiency。本文提供了一种反向分析模板：把 radius/step-size 的 multiplicative update 写成随机级数，证明 bad-event-dominated regime 下总位移有限或过小。

看似新的部分中，Chernoff bound、martingale SLLN、Borel-Cantelli 都是标准工具；实质创新在于把它们放到 PDS 的步长-位移结构里，并识别出 p*=logγ/log(θ^{-1}γ) 正好对应既有收敛阈值的补集。

Dataset / Evaluation

本文不是经验论文，evaluation 的作用很有限。实验只覆盖简单二维二次函数和一维 toy case，目标是验证非收敛现象以及 Theorem 3.3 中幂律下界的形状，而不是证明实际 DFO solver 的广泛失败。

从支撑 claim 的角度看，这足够，因为核心 claim 是理论定理，不依赖 benchmark。实验没有跨真实黑箱任务、没有 noisy objective、没有高维实际应用，也没有和工程实现中的 search step / adaptive polling / opportunistic ordering 做系统比较。因此不能把实验解读为 practical PDS 在真实部署中的 failure rate 估计。

比较有意思的是数值曲线显示下界指数可能 sharp，但文中未充分说明其理论最优性；这部分仍是 conjectural evidence。没有 benchmark leakage 或 data coverage 这类问题，因为本文不是数据驱动方法。

Limitation

最核心限制是凸性。Lemma 3.2 依赖凸性保证“无下降方向 ⇒ 不可能 sufficient decrease”。非凸目标中，即使 d^T∇f≥0，也可能由于曲率在有限步长上下降；因此本文机制不能直接覆盖 practical DFO 最常见的非凸黑箱场景。换言之，理论证明的是一个干净但偏理想化的 failure regime。

第二个限制是结论形式为 positive probability non-convergence，而非 almost-sure failure。它足以否定 global convergence，但对 typical-case behavior 的刻画不完整。实际运行中失败概率多大、如何受 f 的几何结构影响，本文没有完全回答。

第三，边界 case 未解决。m=log2(1-logθ/logγ) 是整个 phase transition 的临界点，既有收敛理论和本文非收敛理论都无法覆盖；一维情形是例外，但一般维度仍开放。

第四，典型实现假设方向独立、均匀、固定 m，且不依赖 history。实际 PDS 可能使用 adaptive sampling、方向重用、启发式 ordering、search step 或并行筛选，这些都会改变 bad-event 概率和 filtration 结构。本文的工具可能可迁移，但结论不能直接外推。

第五，非收敛概率下界的 sharpness 仍未证明。实验暗示幂律指数正确，但常数和精确尾行为不清楚。增益来源不是 engineering，而是理论重建；但 sharp quantitative characterization 仍不完整。

Takeaway

• 1. PDS 的 probabilistic descent condition 对典型均匀随机方向实现基本是必要的；低于方向数阈值时，失败不是证明技术问题，而是算法动力学问题。
• 2. 随机优化中许多 submartingale-like 假设都应被反向审视。
• 本文给了一个可迁移模板：不要只分析 good-event 频率如何推动收敛，也要分析 bad-event 频率如何通过 step-size/radius 乘法过程锁死算法。
• 3. 真正值得迁移的不是 probabilistic ascent 这个定义，而是“轨迹总位移 = success indicators × multiplicative radius series”的视角。

一句话总结

这篇论文把 PDS 的随机方向数阈值从单侧收敛充分条件推进为几乎 sharp 的收敛/非收敛分界，核心贡献是用随机级数机制证明 probabilistic descent 假设对典型实现并非分析 artifact。