Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userConcentration inequalities and performance guarantees for hypocoercive MCMC samplers
60
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper we provide performance guarantees for hypocoercive non-reversible MCMC samplers $X_t$ with invariant measure $mu^*$ and our results apply in particular to the Langevin equation, Hamiltonian Monte-Carlo, and the bouncy particle and zig-zag samplers. Specifically, we establish a concentration inequality of Bernstein type for ergodic averages $frac{1}{T} int_0^T f(X_t), dt$. As a consequence we provide performance guarantees: (a) explicit non-asymptotic confidence intervals for $int f dmu^*$ when using a finite time ergodic average with given initial condition $mu$ and (b) uncertainty quantification bounds, expressed in terms of relative entropy rate, on the bias of $int f dmu^*$ when using an alternative or approximate processes $widetilde{X}_t$. (Results in (b) generalize recent results (arXiv:1812.05174) from the authors for coercive dynamics.) The concentration inequality is proved by combining the approach via Feynmann-Kac semigroups first noted by Wu with the hypocoercive estimates of Dolbeault, Mouhot and Schmeiser (arXiv:1005.1495) developed for the Langevin equation and recently generalized to partially deterministic Markov processes by Andrieu et al. (arXiv:1808.08592)
rate research
Read More
We derive simple concentration inequalities for bounded random vectors, which generalize Hoeffdings inequalities for bounded scalar random variables. As applications, we apply the general results to multinomial and Dirichlet distributions to obtain multivariate concentration inequalities.
Monte Carlo methods are the standard procedure for estimating complicated integrals of multidimensional Bayesian posterior distributions. In this work, we focus on LAIS, a class of adaptive importance samplers where Markov chain Monte Carlo (MCMC) algorithms are employed to drive an underlying multiple importance sampling (IS) scheme. Its power lies in the simplicity of the layered framework: the upper layer locates proposal densities by means of MCMC algorithms; while the lower layer handles the multiple IS scheme, in order to compute the final estimators. The modular nature of LAIS allows for different possible choices in the upper and lower layers, that will have different performance and computational costs. In this work, we propose different enhancements in order to increase the efficiency and reduce the computational cost, of both upper and lower layers. The different variants are essential if we aim to address computational challenges arising in real-world applications, such as highly concentrated posterior distributions (due to large amounts of data, etc.). Hamiltonian-driven importance samplers are presented and tested. Furthermore, we introduce different strategies for designing cheaper schemes, for instance, recycling samples generated in the upper layer and using them in the final estimators in the lower layer. Numerical experiments show the benefits of the proposed schemes as compared to the vanilla version of LAIS and other benchmark methods.
A central tool in the study of nonhomogeneous random matrices, the noncommutative Khintchine inequality of Lust-Piquard and Pisier, yields a nonasymptotic bound on the spectral norm of general Gaussian random matrices $X=sum_i g_i A_i$ where $g_i$ are independent standard Gaussian variables and $A_i$ are matrix coefficients. This bound exhibits a logarithmic dependence on dimension that is sharp when the matrices $A_i$ commute, but often proves to be suboptimal in the presence of noncommutativity. In this paper, we develop nonasymptotic bounds on the spectrum of arbitrary Gaussian random matrices that can capture noncommutativity. These bounds quantify the degree to which the deterministic matrices $A_i$ behave as though they are freely independent. This intrinsic freeness phenomenon provides a powerful tool for the study of various questions that are outside the reach of classical methods of random matrix theory. Our nonasymptotic bounds are easily applicable in concrete situations, and yield sharp results in examples where the noncommutative Khintchine inequality is suboptimal. When combined with a linearization argument, our bounds imply strong asymptotic freeness (in the sense of Haagerup-Thorbj{o}rnsen) for a remarkably general class of Gaussian random matrix models, including matrices that may be very sparse and that lack any special symmetries. Beyond the Gaussian setting, we develop matrix concentration inequalities that capture noncommutativity for general sums of independent random matrices, which arise in many problems of pure and applied mathematics.
We obtain moment and Gaussian bounds for general Lipschitz functions evaluated along the sample path of a Markov chain. We treat Markov chains on general (possibly unbounded) state spaces via a coupling method. If the first moment of the coupling time exists, then we obtain a variance inequality. If a moment of order 1+epsilon of the coupling time exists, then depending on the behavior of the stationary distribution, we obtain higher moment bounds. This immediately implies polynomial concentration inequalities. In the case that a moment of order 1+epsilon is finite uniformly in the starting point of the coupling, we obtain a Gaussian bound. We illustrate the general results with house of cards processes, in which both uniform and non-uniform behavior of moments of the coupling time can occur.
Consider $n$ complex random matrices $X_1,ldots,X_n$ of size $dtimes d$ sampled i.i.d. from a distribution with mean $E[X]=mu$. While the concentration of averages of these matrices is well-studied, the concentration of other functions of such matrices is less clear. One function which arises in the context of stochastic iterative algorithms, like Ojas algorithm for Principal Component Analysis, is the normalized matrix product defined as $prodlimits_{i=1}^{n}left(I + frac{X_i}{n}right).$ Concentration properties of this normalized matrix product were recently studied by cite{HW19}. However, their result is suboptimal in terms of the dependence on the dimension of the matrices as well as the number of samples. In this paper, we present a stronger concentration result for such matrix products which is optimal in $n$ and $d$ up to constant factors. Our proof is based on considering a matrix Doob martingale, controlling the quadratic variation of that martingale, and applying the Matrix Freedman inequality of Tropp cite{TroppIntro15}.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
