精读笔记

Problem Setting

这篇论文实际处理的是 stochastic iterative analysis 中一个很常见但通常被跳过的问题：已有分析经常能证明某个 residual / gap 的加权和有限，例如 ∑α_n ξ_n<∞，也能通过 Robbins–Siegmund 得到 quasi-Fejér 收敛，但这并不自动给出 last-iterate 的点态速率。确定性 Olivier 定理告诉我们，在单调正项可和时可以推出 ξ_n=o(1/n)；带权版本则给出 ξ_n=o(1/θ_n)。问题是随机迭代里 ξ_n 往往既不单调，也不满足路径上的准单调，只满足条件期望意义下的 almost supermartingale 递推。

真正困难点是把“条件期望下降 + summability”变成“路径上单项衰减”。Robbins–Siegmund 可以保证收敛和某些误差可和，但它本身不提供 Olivier 型 rate extraction；Olivier / Abel–Dini 工具能提供 rate extraction，但要求确定性或路径准单调。本文切入的关键矛盾就是：随机算法中最自然的结构是 conditional descent，而 last-iterate 小 o 速率需要某种替代单调性的机制。

Motivation

已有路线不够的地方很明确：随机 quasi-Fejér / Robbins–Siegmund 分析长期擅长证明 almost-sure convergence，却很少给出非遍历 last-iterate rate；而优化文献中的速率结果通常依赖更强结构，例如强凸性、误差界、co-coercivity、有限方差、平均迭代或期望意义分析。对于一般 Hilbert 空间中的 monotone inclusion、nonexpansive fixed point、convex minimization，这些假设往往太强。

作者的核心观察是：很多随机迭代分析已经隐含产生了 Olivier 所需的两个 ingredients：一是某个 residual 的加权可和性，二是某种缩放过程的收敛性。缺的不是新的算法，而是一个 stochastic Olivier transfer lemma，把已有收敛证明中的“副产品”转化为 pointwise asymptotic rate。因此本文更像是在补齐随机迭代理论中的 rate-extraction layer，而不是提出新的优化方法。

Core Idea

论文的真正核心是把 Olivier 定理从“单调序列”提升到“almost supermartingale 控制的随机过程”。具体说，给定 α_n 和 θ_n=∑_{k≤n}α_k，如果 ξ_n 满足条件期望递推 E(ξ_{n+1}|F_n)≤(1+δ_n)ξ_n+ε_n，且误差在 θ_n 尺度下足够可和，那么构造 β_n=θ_n ξ_n 或 β_{n+1}=θ_n ξ_{n+1}。Robbins–Siegmund 负责证明 β_n 几乎处处收敛；Abel / Abel–Dini 负责证明如果极限不是 0，就会与 ∑α_n ξ_n<∞ 矛盾。

本质区别在于，prior 的 Olivier 型结论依赖 ξ_n 本身的单调 / 准单调；本文只要求缩放后的随机过程有 almost-supermartingale 收敛性。这相当于把确定性单调性替换为 filtrated conditional stability。这个替换很重要，因为 stochastic proximal、KM iteration、SGD 的自然分析几乎都给 conditional descent，而不是 sample-path monotonicity。因此它的 generalizability 来自抽象概率结构，而不是某个算法技巧。

Method

第一，Theorem 1.4 是核心工具，解决的是“从加权可和性到 almost-sure last-iterate 小 o 速率”的转换问题。它需要 α_n 发散累积尺度 θ_n、almost supermartingale 递推、δ_n 可和、θ_n ε_n 可和；这些条件保证缩放变量 β_n 收敛，同时误差不会在 θ_n 尺度上污染极限。

第二，证明中真正必要的机制是两步：Robbins–Siegmund 只负责让 β_n 有极限；Abel / Abel–Dini 只负责排除正极限。前者提供随机稳定性，后者提供 rate extraction。二者的组合是本文的主要技术增量。

第三，应用部分不是各自重新发明速率证明，而是把不同算法的 residual 识别为 ξ_n，把步长或松弛强度识别为 α_n，把噪声项压进 ε_n。proximal point 中 ξ_n 是 Yosida residual 的平方；KM 中是 fixed-point displacement 的平方；SGD 中是 objective gap。核心变化是这些算法的标准 Fejér 不等式现在可以直接输出 last-iterate 小 o 速率。

第四，期望范数结论依赖 Theorem 1.4(iii) 的额外 uniform integrability 风格 argument，即先控制 E(θ_n ξ_n) 的有界性，再由 ξ_n θ_n→0 a.s. 推 E√(θ_n ξ_n)→0。这部分是辅助增强，不是主贡献。

Key Insight / Why It Works

最关键的 insight 是：Olivier 定理真正需要的不是 ξ_n 单调，而是 θ_n ξ_n 有极限。一旦缩放后的量收敛，若极限为正，则 ξ_n 至少像常数 / θ_n 那样大；乘上 α_n 后，∑α_n ξ_n 会因为 ∑α_n/θ_n=∞ 而发散。这就是整个结果成立的核心逻辑。单调性在经典 Olivier 中只是保证缩放极限行为的一种方式；本文用 almost supermartingale 收敛替代它。

最可能的核心贡献是 Theorem 1.4 的抽象形式及其证明范式，而不是后面的算法本身。应用部分的价值在于展示很多 stochastic iteration 的 rate 可以“免费”从已有 Fejér 分析中抽取出来。换言之，增益主要来自 proof abstraction / rate-transfer，而不是新的 algorithmic scaling、data coverage、representation alignment 或 test-time compute。

有些部分更像辅助工程化的数学封装。例如不同算法中的 ε_n 条件看起来复杂，但本质都是为了满足 ∑θ_n ε_n<∞；随机松弛中的独立性假设也是为了让条件期望可分解。它们不是新的机制，只是让主定理可套用的 bookkeeping。

SGD 部分值得单独判断：得到的是一般 convex smooth 下 almost-sure objective gap last-iterate 小 o 速率，但步长要求 p>2/3，本质原因是需要 ∑θ_n γ_n^2<∞。这不是 SGD 特有的新优化机制，而是 Olivier transfer 对噪声尾项可和性的要求。速率来自步长尺度 θ_n，而不是更强的几何性质。

Relation To Prior Work

这篇最接近两条谱系：一条是 Olivier / Abel–Dini / quasi-monotone sequence 的确定性级数理论；另一条是 Robbins–Siegmund / stochastic quasi-Fejér 的随机迭代收敛理论。本文的实质创新就是把这两条线接起来：用 Robbins–Siegmund 生成 Olivier 所需的缩放收敛性，再用 Abel–Dini 排除正极限。

和传统 stochastic approximation rate work 相比，它不追求 finite-time expectation bound，也不依赖强凸或误差界；它输出的是 almost-sure last-iterate little-o rate。和 deterministic proximal / KM rate work 相比，它不需要路径单调 residual，而允许条件期望意义下的随机扰动。和近期 quantitative Robbins–Siegmund 相比，本文不是 quantitative bound，而是 asymptotic rate extraction。

看似新的算法结论，很多其实是已有 Fejér inequalities 的重组：proximal point、KM、SGD 的递推结构都很经典。真正新增的信息是：这些递推一旦满足加权噪声可和条件，就自动蕴含 last-iterate 小 o 速率。尤其 proximal point 中 Yosida approximation 的速率被作者指出即使在 deterministic setting 也有新意，这部分是应用层面的实质新增。

Dataset / Evaluation

没有 dataset，也没有 empirical evaluation；这是纯理论论文。评价方式是将主定理应用到四类随机迭代：inexact proximal point、stochastic proximal minimization、randomly relaxed inexact Krasnosel'skii–Mann、stochastic gradient method。覆盖面较广，说明主引理不是为单一算法定制。

这些应用基本支持论文的核心 claim：almost-supermartingale Olivier extension 可以系统地产生随机迭代的 almost-sure convergence rates。但它们验证的是数学可迁移性，不是实际算法性能。没有真实世界任务、没有数值实验、没有比较不同噪声规模下的 tightness，也没有说明这些小 o 速率在 finite horizon 是否可见。

因此 evaluation 的强项是抽象统一性，弱项是 rate sharpness 与 practical relevance 文中未充分说明。尤其小 o 结论没有常数，无法直接判断是否优于已有期望界或 ergodic bound 的实际可用性。

Limitation

第一，框架的核心前提是加权可和性已经可得。Theorem 1.4 本身不告诉你如何证明 ∑α_n ξ_n<∞；在应用中这通常仍依赖传统 Fejér / descent argument。因此它不是替代收敛分析，而是收敛分析之后的 rate extraction layer。

第二，误差条件偏强，尤其 ∑θ_n ε_n<∞ 会随着目标速率变快而快速收紧。SGD 中 p>2/3 就是典型表现：为了让 θ_n γ_n^2 可和，步长不能太慢衰减。这说明速率不是免费来自随机结构，而是用更强的噪声尾部控制换来的。

第三，独立性假设在一些 stochastic control / Markovian noise 场景下不自然。KM 随机松弛要求 μ_n 独立于历史和误差；Theorem 1.4(iii) 的期望结论要求 δ_n 与 (ξ_n,θ_n) 独立。这些假设让证明干净，但限制了 adaptive relaxation、state-dependent sampling、Markovian oracle 的适用性。

第四，结论是 asymptotic little-o，不是 tight rate、复杂度界或高概率界。它能说明最终比 1/θ_n 快，但不能说明何时进入该 regime，也不能比较不同算法常数。实际部署中的 finite-time gap 仍未被解决。

第五，SGD 部分的泛化性有限：convex smooth、共同 Lipschitz gradient、variance controlled by ψ(||x||)、a.s. boundedness 由 Robbins–Siegmund 推出。对现代非凸、重尾噪声、数据相关 sampling 的解释力有限。这里没有 benchmark leakage 或 hidden supervision 问题，因为无实验；但 practical gain 的归因也不清晰。

Takeaway

• 1. 最值得记住的是替换原则：Olivier 需要的不是单调性，而是缩放过程 θ_n ξ_n 的收敛性；almost supermartingale 正好提供这种替代结构。
• 2. 这篇论文真正推动的是 stochastic iteration theory 的 last-iterate asymptotic-rate extraction，而不是提出新算法。
• 以后很多 quasi-Fejér 分析都可以检查是否能直接套这个模板。
• 3. 可迁移 insight 是：先证明 residual 的加权可和，再证明缩放 residual 的 almost-supermartingale 收敛，最后用 Abel–Dini 排除正极限。

一句话总结

《Almost Supermartingale Extensions of Olivier's Theorem》（arXiv preprint / 2026-07-03）把 Olivier 的确定性 rate-extraction 原理嵌入 Robbins–Siegmund almost-supermartingale 框架，为随机迭代提供了一种统一的 almost-sure last-iterate 小 o 速率工具，贡献主要是理论抽象而非新算法。