The Guided Speed

The random walk Metropolis algorithm proposes a move by adding symmetric noise to the current state: x’ = x + z. The guided walk Metropolis proposes a move that knows where it’s going: x’ = x + z + drift. Both converge to the target distribution. How much faster is guidance?

For polynomial-tailed targets — distributions that decay as |x|^{-α} — the guided walk converges at twice the polynomial rate of the random walk. Not twice as fast in wall-clock time. Twice the rate in the exponent that governs tail exploration. When the state variable is large, the guided walk moves ballistically toward the center while the random walk meanders.

But under strictly convex potentials — distributions like e^{-|x|^p} where the tails decay faster than polynomial — the picture changes. Here the random walk Metropolis behaves as a half-lazy version of the guided walk. They move at the same ballistic speed; the random walk just wastes half its proposals doing nothing. The gap between them shrinks from a rate difference to a constant factor.

The structural insight: guidance helps most where the tails are heavy. In light-tailed distributions, the geometry of the potential already pushes the sampler toward the center — curvature does the guiding for free. In heavy-tailed distributions, the landscape is nearly flat in the tails, so there’s no geometric signal to exploit. The drift term provides what the geometry lacks. The value of guidance is inversely proportional to the information the target already provides about where to go.

The conditions required for these results are “stronger than might be expected” — the authors prove by counterexample that they’re necessary. Even guidance can’t help if the problem lacks the regularity that guidance exploits.