Beyond Well-Tempered Metadynamics algorithms for sampling multimodal target densities

In many situations, sampling methods are considered in order to compute expectations with respect to a distribution $\pi \, d\lambda$ on $X \subset \mathbb{R}^D$ , when $\pi$ is highly multimodal. Free-energy based adaptive importance sampling techniques have been developed in the physics and chemistry literature to efficiently sample from such a target distribution. These methods are casted in the class of adaptive Markov chain Monte Carlo (MCMC) samplers: at each iteration, a sample approximating a biased distribution is drawn and the biasing strategy is learnt on the fly. As usual with importance sampling, expectations with respect to $\pi$ are obtained from a weighted mean of the samples returned by the sampler. Examples of such approaches are Wang-Landau algorithms, the Self-Healing Umbrella Sampling, adaptive biasing forces methods, the metadynamic algorithm or the well-tempered metadynamics algorithm. Nevertheless, the main drawback of most of these methods is that two antagonistic phenomena are in competition: on one hand, a mechanism to overcome the multimodality issue which is defined to force the sampler to visit a given set of strata of the space equally; on the other hand, the algorithm spends the same time in strata with high and low weight under $\pi \, d\lambda$ which makes the Monte Carlo approximation of expectations under $\pi \, d\lambda$ quite inefficient. We present a new algorithm, which generalizes all the examples mentioned above: this novel algorithm is designed to reduce the two antagonistic effects. We will show that the estimation of the local bias can be seen as a Stochastic Approximation algorithm with random step-size sequence; and the sampler as an adaptive MCMC method. We will analyze its asymptotic behavior and discuss numerically the role of some design parameters. Joint work with B. Jourdain, T. Lelièvre and G. Stoltz (from ENPC, France).Non UBCUnreviewedAuthor affiliation: Institut de Mathématiques de Toulouse & Centre National de la Recherche ScientifiqueResearche