We investigate the properties of the Hybrid Monte-Carlo algorithm (HMC) in
high dimensions. HMC develops a Markov chain reversible w.r.t. a given target
distribution $Pi$ by using separable Hamiltonian dynamics with potential
$-logPi$. The additional momentum variables are chosen at random from the
Boltzmann distribution and the continuous-time Hamiltonian dynamics are then
discretised using the leapfrog scheme. The induced bias is removed via a
Metropolis-Hastings accept/reject rule. In the simplified scenario of
independent, identically distributed components, we prove that, to obtain an
$mathcal{O}(1)$ acceptance probability as the dimension $d$ of the state space
tends to $infty$, the leapfrog step-size $h$ should be scaled as $h= l imes
d^{-1/4}$. Therefore, in high dimensions, HMC requires $mathcal{O}(d^{1/4})$
steps to traverse the state space. We also identify analytically the
asymptotically optimal acceptance probability, which turns out to be 0.651 (to
three decimal places). This is the choice which optimally balances the cost of
generating a proposal, which {em decreases} as $l$ increases, against the cost
related to the average number of proposals required to obtain acceptance, which
{em increases} as $l$ increases.
martes, 26 de enero de 2010
Optimal tuning of the Hybrid Monte-Carlo Algorithm. (arXiv:1001.4460v1 [math.PR])
Solving Schubert Problems with Littlewood-Richardson Homotopies. (arXiv:1001.4125v1 [math.NA])
We present a new numerical homotopy continuation algorithm for finding all
solutions to Schubert problems on Grassmannians. This Littlewood-Richardson
homotopy is based on Vakil's geometric proof of the Littlewood-Richardson rule.
Its start solutions are given by linear equations and they are tracked through
a sequence of homotopies encoded by certain checker configurations to find the
solutions to a given Schubert problem. For generic Schubert problems the number
of paths tracked is optimal. The Littlewood-Richardson homotopy algorithm is
implemented using the path trackers of the software package PHCpack.
Numerical Studies of Three-dimensional Stochastic Darcy’s Equation and Stochastic Advection-Diffusion-Dispersion Equation
A Compact Fourth Order Scheme for the Helmholtz Equation in Polar Coordinates
A note on the O(n)-storage implementation of the GKO algorithm and its adaptation to Trummer-like matrices
An O(h6) numerical solution of general nonlinear fifth-order two point boundary value problems
A variable step-size control algorithm for the weak approximation of stochastic differential equations
A binary powering Schur algorithm for computing primary matrix roots
A Kantorovich-type convergence analysis of the Newton–Josephy method for solving variational inequalities
- Journal Numerical Algorithms
- Online ISSN 1572-9265
- Print ISSN 1017-1398
- Journal Volume Volume -1
- Journal Issue Volume -1, Online First / January, 2010
Suscribirse a:
Entradas (Atom)