Probabilistic Contraction Analysis of Iterated Random Operators

• URL: http://arxiv.org/abs/1804.01195v6
• Date: Fri, 22 Sep 2023 01:02:14 GMT
• Title: Probabilistic Contraction Analysis of Iterated Random Operators
• Authors: Abhishek Gupta and Rahul Jain and Peter Glynn
• Abstract summary: 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.
• Score: 10.442391859219807
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In many branches of engineering, Banach contraction mapping theorem is employed to establish the convergence of certain deterministic algorithms. Randomized versions of these algorithms have been developed that have proved useful in data-driven problems. 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. In this paper, we develop a new stochastic dominance based proof technique, called probabilistic contraction analysis, for establishing the convergence in probability of Markov chains generated by such iterated random operators in certain limiting regime. The methods developed in this paper provides a general framework for understanding convergence of a wide variety of Monte Carlo methods in which contractive property is present. We apply the convergence result to conclude the convergence of fitted value iteration and fitted relative value iteration in continuous state and continuous action Markov decision problems as representative applications of the general framework developed here.

Related papers

• Tree-structured Markov random fields with Poisson marginal distributions [0.0]
  A new family of tree-structured random fields for a vector of discrete counting random variables is introduced. The marginal Poisson random fields are all with the same mean, and are untied from the strength or structure of their built-in dependence.
  arXiv  Detail & Related papers  (2024-08-24T18:30:15Z)
• 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)
• A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms [14.33758865948252]
  We revisit two famous bandit algorithms, Minimum Empirical Divergence (MED) and Thompson Sampling (TS) We prove that MED is optimal for all these models, but also provide a simple regret analysis of some TS algorithms for which the optimality is already known.
  arXiv  Detail & Related papers  (2023-03-10T16:43:48Z)
• 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)
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective [30.524043513721168]
  We develop a general recipe for analyzing the convergence of iterative algorithms for a class of regression models. deterministicly, we accurately capture both the convergence rate of the algorithm and the eventual error floor in the finite-sample regime. We show sharp convergence rates for both higher-order algorithms based on alternating updates and first-order algorithms based on subgradient subgradients.
  arXiv  Detail & Related papers  (2021-09-20T21:48:19Z)
• A greedy reconstruction algorithm for the identification of spin distribution [0.0]
  We show that the identifiability of a piecewise constant approximation of the probability distribution is related to the invertibility of a matrix. The algorithm aims to design specific controls which ensure that this matrix is as far as possible from a singular matrix.
  arXiv  Detail & Related papers  (2021-08-26T12:40:52Z)
• The Connection between Discrete- and Continuous-Time Descriptions of Gaussian Continuous Processes [60.35125735474386]
  We show that discretizations yielding consistent estimators have the property of invariance under coarse-graining' This result explains why combining differencing schemes for derivatives reconstruction and local-in-time inference approaches does not work for time series analysis of second or higher order differential equations.
  arXiv  Detail & Related papers  (2021-01-16T17:11:02Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
  arXiv  Detail & Related papers  (2020-06-11T19:40:38Z)
• 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)
• Convergence of Recursive Stochastic Algorithms using Wasserstein Divergence [4.688616907736838]
  We show that convergence of a large family of constant stepsize RSAs can be understood using this framework. We show that convergence of a large family of constant stepsize RSAs can be understood using this framework.
  arXiv  Detail & Related papers  (2020-03-25T13:45:16Z)

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.