给出随机优化中关键定理的定量版本，可估算收敛所需步数。
A quantitative Robbins-Siegmund theorem
- 构建了李1-上鞅的类稳态版多布定理，用于量化分析
- 首次提供稳态区域定位所需的步数上界
- 适用于依赖罗宾斯-西格蒙德定理的各类随机算法
罗宾斯-西格蒙德定理是随机优化中最重要结果之一，广泛用于证明随机算法的收敛性。本文提供了该定理的定量版本，建立了在陶哲轩定义的'稳态'意义下，确定所需观察步数以定位稳态区域的上界。证明过程涉及李1-上鞅的类稳态多布定理，以及一系列技术引理，精确刻画了随机过程中定量信息如何通过求和与乘积传播。本研究建立了一种通用方法，可用于将能归约为上鞅的随机过程的稳态边界，从而为大量依赖罗宾斯-西格蒙德定理变体进行收敛性证明的随机算法，提供定量收敛信息。最后讨论了该结果在实际中的应用可能。
原文摘要 · Abstract (English)
The Robbins-Siegmund theorem is one of the most important results in stochastic optimization, where it is widely used to prove the convergence of stochastic algorithms. We provide a quantitative version of the theorem, establishing a bound on how far one needs to look in order to locate a region of \emph{metastability} in the sense of Tao. Our proof involves a metastable analogue of Doob's theorem for $L_1$-supermartingales along with a series of technical lemmas that make precise how quantitative information propagates through sums and products of stochastic processes. In this way, our paper establishes a general methodology for finding metastable bounds for stochastic processes that can be reduced to supermartingales, and therefore for obtaining quantitative convergence information across a broad class of stochastic algorithms whose convergence proof relies on some variation of the Robbins-Siegmund theorem. We conclude by discussing how our general quantitative result might be used in practice.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。