A quantitative Robbins-Siegmund theorem

• URL: http://arxiv.org/abs/2410.15986v1
• Date: Mon, 21 Oct 2024 13:16:29 GMT
• Title: A quantitative Robbins-Siegmund theorem
• Authors: Morenikeji Neri, Thomas Powell,
• Abstract summary: We provide a quantitative version of the Robbins-Siegmund 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_$-supermartingales along with a series of technical lemmas that make precise how quantitative information propagates through sums and products of processes.
• Score: 0.0
• License:
• Abstract: 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.

Related papers

• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  Proximal point methods have attracted considerable interest owing to their numerical stability and robustness against imperfect tuning. This paper presents a comprehensive analysis of a broad range of variations of the proximal point method (SPPM)
  arXiv  Detail & Related papers  (2024-05-24T21:09:19Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  We propose a family of Riemannian algorithms generalizing and extending the seminal approximation framework of Robbins and Monro. Compared to their Euclidean counterparts, Riemannian algorithms are much less understood due to lack of a global linear structure on the manifold. We provide a general template of almost sure convergence results that mirrors and extends the existing theory for Euclidean Robbins-Monro schemes.
  arXiv  Detail & Related papers  (2022-06-14T12:30:11Z)
• A Unified Convergence Theorem for Stochastic Optimization Methods [4.94128206910124]
  We provide a fundamental unified convergence theorem used for deriving convergence results for a series of unified optimization methods. As a direct application, we recover almost sure convergence results under general settings.
  arXiv  Detail & Related papers  (2022-06-08T14:01:42Z)
• Gaussian Processes and Statistical Decision-making in Non-Euclidean Spaces [96.53463532832939]
  We develop techniques for broadening the applicability of Gaussian processes. We introduce a wide class of efficient approximations built from this viewpoint. We develop a collection of Gaussian process models over non-Euclidean spaces.
  arXiv  Detail & Related papers  (2022-02-22T01:42:57Z)
• Formalization of a Stochastic Approximation Theorem [0.22940141855172028]
  approximation algorithms are iterative procedures which are used to approximate a target value in an environment where the target is unknown. Originally introduced in a 1951 paper by Robbins and Monro, the field of approximation has grown enormously and has come to influence application domains.
  arXiv  Detail & Related papers  (2022-02-12T02:31:14Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  We analyze a Newton algorithm for homogeneous distributed convex optimization, where each machine can calculate gradients of the same population objective. We show that our method can reduce the number, and frequency, of required communication rounds compared to existing methods without hurting performance.
  arXiv  Detail & Related papers  (2021-10-07T17:51:10Z)
• On the Convergence of Reinforcement Learning with Monte Carlo Exploring Starts [5.137144629366217]
  A basic simulation-based reinforcement learning algorithm is the Monte Carlo Exploring States (MCES) method. We investigate the convergence of this algorithm for the case with undiscounted costs, also known as the shortest path problem. As a side result, we also provide a proof of a version of the supermartingale convergence theorem commonly used in approximation.
  arXiv  Detail & Related papers  (2020-07-21T16:19:09Z)
• A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms [67.67377846416106]
  We present a distributional approach to theoretical analyses of reinforcement learning algorithms for constant step-sizes. We show that value-based methods such as TD($lambda$) and $Q$-Learning have update rules which are contractive in the space of distributions of functions.
  arXiv  Detail & Related papers  (2020-03-27T05:13:29Z)
• Probabilistic Contraction Analysis of Iterated Random Operators [10.442391859219807]
  Banach contraction mapping theorem is employed to establish the convergence of certain deterministic algorithms. In a class of randomized algorithms, in each iteration, the contraction map is approximated with an operator that uses independent and identically distributed samples of certain random variables. This leads to iterated random operators acting on an initial point in a complete metric space, and it generates a Markov chain.
  arXiv  Detail & Related papers  (2018-04-04T00:10:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.