Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation

• URL: http://arxiv.org/abs/2002.02584v1
• Date: Fri, 7 Feb 2020 01:52:21 GMT
• Title: Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation
• Authors: Shuhang Chen, Adithya M. Devraj, Ana Bu\v{s}i\'c, Sean Meyn
• Abstract summary: It is not possible to obtain a Hoeffding bound on the error sequence, even when the underlying Markov chain is reversible and geometrically ergodic. It is shown that mean square error achieves the optimal rate of $O(1/n)$, subject to conditions on the step-size sequence.
• Score: 4.817429789586127
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper concerns error bounds for recursive equations subject to Markovian disturbances. Motivating examples abound within the fields of Markov chain Monte Carlo (MCMC) and Reinforcement Learning (RL), and many of these algorithms can be interpreted as special cases of stochastic approximation (SA). It is argued that it is not possible in general to obtain a Hoeffding bound on the error sequence, even when the underlying Markov chain is reversible and geometrically ergodic, such as the M/M/1 queue. This is motivation for the focus on mean square error bounds for parameter estimates. It is shown that mean square error achieves the optimal rate of $O(1/n)$, subject to conditions on the step-size sequence. Moreover, the exact constants in the rate are obtained, which is of great value in algorithm design.

Related papers

• Maximum a Posteriori Inference for Factor Graphs via Benders' Decomposition [0.38233569758620056]
  We present a method for maximum a-posteriori inference in general Bayesian factor models. We derive MAP estimation algorithms for the Bayesian Gaussian mixture model and latent Dirichlet allocation.
  arXiv  Detail & Related papers  (2024-10-24T19:57:56Z)
• Randomized Physics-Informed Machine Learning for Uncertainty Quantification in High-Dimensional Inverse Problems [49.1574468325115]
  We propose a physics-informed machine learning method for uncertainty quantification in high-dimensional inverse problems. We show analytically and through comparison with Hamiltonian Monte Carlo that the rPICKLE posterior converges to the true posterior given by the Bayes rule.
  arXiv  Detail & Related papers  (2023-12-11T07:33:16Z)
• Interfacing branching random walks with Metropolis sampling: constraint release in auxiliary-field quantum Monte Carlo [8.618234453116251]
  We present an approach to interface branching random walks with Markov chain Monte Carlo sampling. We use the generalized Metropolis algorithm to sample a selected portion of the imaginary-time path after it has been produced by the branching random walk.
  arXiv  Detail & Related papers  (2023-05-16T16:12:56Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. We establish non-asymptotic bounds for both the operator defect and the estimation error.
  arXiv  Detail & Related papers  (2022-01-21T02:46:57Z)
• Asymptotic bias of inexact Markov Chain Monte Carlo methods in high dimension [0.7614628596146599]
  Examples include the unadjusted Langevin (ULA) and unadjusted Hamiltonian Monte Carlo (uHMC) We show that for both ULA and uHMC, the bias depends on key quantities related to the target distribution or the stationary probability measure of the scheme.
  arXiv  Detail & Related papers  (2021-08-02T07:34:09Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  We consider the problem of learning the optimal policy for infinite-horizon Markov decision processes (MDPs) Some variant of Mirror Descent is proposed for convex programming problems with Lipschitz-continuous functionals. We analyze this algorithm in a general case and obtain an estimate of the convergence rate that does not accumulate errors during the operation of the method.
  arXiv  Detail & Related papers  (2021-02-27T19:28:39Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  We propose the amortized conditional normalized maximum likelihood (ACNML) method as a scalable general-purpose approach for uncertainty estimation. Our algorithm builds on the conditional normalized maximum likelihood (CNML) coding scheme, which has minimax optimal properties according to the minimum description length principle. We demonstrate that ACNML compares favorably to a number of prior techniques for uncertainty estimation in terms of calibration on out-of-distribution inputs.
  arXiv  Detail & Related papers  (2020-11-05T08:04:34Z)
• Stochastic Learning for Sparse Discrete Markov Random Fields with Controlled Gradient Approximation Error [10.381976180143328]
  We study the $L_$-regularized maximum likelihood estimator/estimation (MLE) problem for discrete Markov random fields (MRFs) To address these challenges, we consider a verifiable learning framework called proximal gradient (SPG) We provide novel verifiable bounds to inspect and control the quality of the gradient approximation.
  arXiv  Detail & Related papers  (2020-05-12T22:48:42Z)

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.