A quantitative Robbins-Siegmund theorem
원문 초록
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 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.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Adaptive Semantic Token Communication for Transformer-based Edge Inference
Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method
JaxSGMC: Modular stochastic gradient MCMC in JAX
SIM-Shapley: A Stable and Computationally Efficient Approach to Shapley Value Approximation
Adversarial Subspace Generation for Outlier Detection in High-Dimensional Data
CatCMA with Margin: Stochastic Optimization for Continuous, Integer, and Categorical Variables
토론
이 논문과 연결된 포럼 글이 아직 없습니다.