A Chevallier
email: chevallier.augustin@gmail.com

F Cazals

Wang-Landau Algorithm: an adapted random walk to boost convergence

Keywords: density of states, numerical integration, stochastic sampling, MCMC, importance sampling, Wang-Landau, high dimensional spaces, random walks, scientific software

The Wang-Landau (WL) algorithm is a recently developed stochastic algorithm computing densities of states of a physical system, and also performing numerical integration in high dimensional spaces. Since its inception, it has been used on a variety of (bio-)physical systems, and in selected cases, its convergence has been proved. The convergence speed of the algorithm is tightly tied to the connectivity properties of the underlying random walk.

As such, we propose an efficient random walk that uses geometrical information to circumvent the following inherent difficulties: avoiding overstepping strata, toning down concentration phenomena in high-dimensional spaces, and accommodating multidimensional distributions. These improvements are especially well suited to improve calculations on a per basin basis -included anharmonic ones.

Experiments on various models stress the importance of these improvements to make WL effective in challenging cases. Altogether, these improvements make it possible to compute density of states for regions of the phase space of small biomolecules.

1 Introduction

The Wang-Landau algorithm

The Wang-Landau algorithm for density of states calculations. The derivation of observable properties of (bio-)molecular systems at thermodynamic equilibrium relies on statistical physics, with the formalism of stochastic ensembles playing a pivotal role [START_REF] Wales | Energy Landscapes[END_REF][START_REF] Lelièvre | Free energy computations: A mathematical perspective[END_REF][START_REF] Janke | Monte Carlo simulations in statistical physics: From basic principles to advanced applications[END_REF][START_REF] Landau | A guide to Monte Carlo simulations in statistical physics[END_REF]. Amidst the various algorithms available, the Wang-Landau (WL) algorithm [START_REF] Wang | Efficient, multiple-range random walk algorithm to calculate the density of states[END_REF][START_REF] Landau | A new approach to Monte Carlo simulations in statistical physics: Wang-Landau sampling[END_REF] is now well known and widely used despite its recent inception, in particular due to its simplicity and genericity. The WL algorithm estimates the density of states (DOS) of a system, namely the number of states (volume in phase space) of the system available at each energy level (whence the term density), which is especially useful to compute partition functions in statistical physics, and more generally observables-e.g. the average energy or the heat capacity. Estimating the DOS is especially challenging in presence of broken ergodicity; in that case, the presence of multiple energy wells prevents the system to efficiently sample the potential energy landscape (PEL), as it remains confined in selected wells [START_REF] Palmer | Broken ergodicity[END_REF][START_REF] Wales | Observation time scale, free-energy landscapes, and molecular symmetry[END_REF].

To review previous work, it is important to recall that the WL algorithm falls in the realm of adaptive Monte Carlo Markov Chain (MCMC) sampling algorithms. In a nutshell, WL returns an estimation of the DOS in terms of histogram. The bins of the histogram correspond to a partitioning of the energy range of the system. The algorithm resorts to importance sampling, using a biasing function derived from the current estimation of the DOS. Since the limit distribution sought is defined by the density of states, the random walk is built from the Metropolis-Hastings algorithm (M-H) [START_REF] Hastings | Monte carlo sampling methods using markov chains and their applications[END_REF], using the current DOS estimate in the rejection rate. (We note in passing that since the DOS values used to define transition probability depend on the history, WL is not a Markov process.) Additionally, a so-called flat histogram rule may be used to count the visits in each energy stratum and update the learning rate when all strata have been evenly visited. These main ingredients recalled, one may observe that numerous improvements were made to the original algorithm [START_REF] Wang | Efficient, multiple-range random walk algorithm to calculate the density of states[END_REF], both in terms of design and analysis of performances. The first key improvement has been the 1/t algorithm which solved the so-called error saturation problem [START_REF] Belardinelli | Fast algorithm to calculate density of states[END_REF][START_REF] Belardinelli | Wang-Landau algorithm: A theoretical analysis of the saturation of the error[END_REF], in which a constant error on DOS estimates was incurred, due to a too fast reduction of the learning rate. Another key initiative has been to tune the random walk / proposal and the energy discretization [START_REF] Bornn | An adaptive interacting Wang-Landau algorithm for automatic density exploration[END_REF], as large bins may hinder convergence by keeping the system trapped. To avoid this pitfall, a dynamic maintenance of bins has been proposed, in order to maintain a proper balance of samples across a stratum. Concomitantly, a proposal defined from a mixture of Gaussians has been introduced, in order to attempt moves of the proper size. In a different vein, it has been proposed to speed up convergence resorting to parallelism via multiple walkers [START_REF] Landau | A new approach to Monte Carlo simulations in statistical physics: Wang-Landau sampling[END_REF]. However, this approach should be taken with care, as problems arise when a large number of walkers are used [START_REF] Belardinelli | Nonconvergence of the Wang-Landau algorithms with multiple random walkers[END_REF].

On the mathematical side, for the WL algorithm variant using the flat histogram, the importance of the analytical form of the DOS update rule was established [START_REF] Jacob | The Wang-Landau algorithm reaches the flat histogram criterion in finite time[END_REF]. For WL with a deterministic adaptation of the learning rate, to which the 1/t variant belongs, the correctness of the DOS estimates was proved, regardless of the particular analytical expression of the update rule [START_REF] Fort | Convergence of the Wang-Landau algorithm[END_REF].

Applications. Application-wise, WL has been used on a variety of physical systems, and more recently to biomolecules. Thermodynamics properties of RNA secondary structures were estimated using the WL algorithm [START_REF] Lou | Thermodynamics of RNA structures by wang-landau sampling[END_REF]. Properties of clusters and peptides (up to 8 a.a.) were studied in [START_REF] Poulain | Performances of Wang-Landau algorithms for continuous systems[END_REF]. Likewise, the thermodynamics properties of misfolded (containing a helix structure rather than a β-sheet) proteins, such as those involved in mad cow and Creutzfeldt-Jakob diseases, were studied by feeding a coarse grain protein to the 1/t WL algorithm variant [START_REF] Ojeda | Electric field-driven disruption of a native β-sheet protein conformation and generation of a helix-structure[END_REF]. In a similar spirit, a modified flat rule histogram was used in [START_REF] Swetnam | Improving the wang-landau algorithm for polymers and proteins[END_REF] to study properties of polymers on a lattice, in the HP model. However, processing continuous models of protein of significant size has remained out of reach so far [START_REF] Janke | Thermodynamics and structure of macromolecules from flat-histogram Monte Carlo simulations[END_REF].

Contributions

The proposal used to generate candidate conformations and the energy discretization influence one another: the average step size of the proposal should be dependent on the size energy bins. For large energy strata, the step size should be large, and small for narrow energy bins. Thus the proposal and bin sizes should not be independent, and the step size of the random walk should depend on local information. Such intricacies have precluded the development of effective WL algorithms to to handle systems as complex as bio-molecules. We make a step into this direction, as this paper focuses on the design of proposals improving the convergence speed of the algorithm, especially in high dimensional settings.

More specifically, we make three contributions. First, we design a proposal to avoid overstepping strata (section 3.3), using information on the level set surfaces bounding the strata. Second, we design a proposal to avoid congestion-i.e. remaining stuck in a stratum, a difficulty faced to move downward towards a local minimum or upward towards a local maximum. This proposal uses a heuristic based on cones to fight measure concentration problems inherent to high dimensional spaces (section 3.4). Finally, we introduce a darting move for multimodal distributions (section 3.5).

2 The Wang-Landau algorithm

Problem statement

We first introduce some classical notations [START_REF] Fort | Convergence of the Wang-Landau algorithm[END_REF]. Consider a bounded subset E ⊂ R n endowed with the Lebesgue measure λ as a reference. Consider also a probability distribution π with density π(x) with respect to the Lebesgue measure. Denoting U : E → R D a real valued function, consider a discretization

U 0 < U 1 < • • • < U d of
its range, with possibly U 0 = -∞ and U d = +∞. Also consider the partition of E into so-called strata {E 1 , . . . , E d }, defined as the pre-images of the potential energy, namely the strata E i are

E i = {x ∈ E|U (x) ∈ [U i-1 , U i )}.
Our problem is to estimate

θ * i Def = Ei π(x)λ(dx), ∀i = 1, . . . , d. (1)
Note that Eq. ( 1) is actually π(E i ), the probability of E i with respect to π. This problem arises in many areas of science and engineering, two of which are discussed below.

Statistical physics: partition function. In this setting, the function U is the potential energy of a physical system. The distribution π stands for Boltzmann's distribution, that is, with β = 1/(k B T ) the inverse temperature (and k B Boltzmann's constant):

π(x) = Z -1 β exp(-βU (x)), with Z β = E exp(-βU (x))dx. (2)
Note that Z β is the so-called partition function of the system. In this context, Eq. (1) reads as

θ * i = Z -1 β Ei exp(-βU (x)
)dx, and one has i θ * i = 1. The WL algorithm computes estimates θ i for θ * i , which also satisfy i θ i = 1. The individual quantities θ i are of interest since their values provide the relative weights of the strata. However, they do not give access to the partition function Z β itself, whose calculation requires a re-normalization.

It should also be noticed that incorporating Boltzmann's factor π into Eq. (1) results in quantities θ i which depend on the particular temperature used.

Statistical physics: density of states. To avoid the aforementioned temperature dependence, we use

π(x) = 1/λ(E), (3)
so that Eq. ( 1) yields

θ * i = λ(E i )/λ(E). (4)
The relative volume of the i-th stratum can then be used to estimate the partition function at any temperature, using a calculation akin to numerical integration. Practically, Eq. ( 4) is the target of our experiments.

Numerical integration. A closely related problem is the calculation of a D-dimensional integral

I D = E f (x)dx. ( 5
)
Assume that the range Y f = [y min , y max ] spanned by f in the domain I is known, and that this interval has been split into n interval [y i , y i + dy]. Consider the estimates from Eq. ( 1) with π(x) = 1/λ(E). Assume that WL has been run, and denote y i the average value of function f computed over all points such that f (x) ∈ [y i , y i + dy]. The integral can be estimated as [START_REF] Atisattaponga | A 1/t algorithm with the density of two states for estimating multidimensional integrals[END_REF] I ≈ i=1,...,n

θ N orm i y i , with θ N orm i = λ(E)θ i . (6)

Algorithm

Sampling from a probability distribution µ. Assume we wish to sample a target distribution µ. We assume the existence of a proposal q on E with probability density q(x, •) -a transition starting from x.

Using the Metropolis-Hastings transition kernel for general state spaces, and denoting δ x a point mass at x, we introduce a random walk P µ whose limiting distribution is µ -see [START_REF] Meyn | Markov chains and stochastic stability[END_REF]Section 3.4] and [START_REF] Tierney | A note on Metropolis-Hastings kernels for general state spaces[END_REF]:

P µ (x, dy) = q(x, y)α(x, y)dy + δ x (dy) E (1 -α(x, z
))q(x, dz), α(x, y) = min(1, µ(y)q(y,x) µ(x)q(x,y) ). [START_REF] Palmer | Broken ergodicity[END_REF] with α(x, y) the acceptance probability of the new state y. Note that the correction factor q(y,x) /q(x,y) allows q to be non-symmetric, a feature used extensively thereafter.

Algorithm. Consider the strata E i defined above, as well as the mapping J : E → {1, . . . , d} returning the index J(x) of the stratum containing x.

The WL algorithm iteratively construct a sequence θ(t) = (θ 1 (t), ..., θ d (t)) of estimates for the unknown vector θ * = (θ * 1 , ..., θ * d ) defined from Eq. ( 1). (NB: for the sake of conciseness, we drop the index t, as the time dependency is implicit.) For an estimate θ, we introduce the piecewise continuous probability density

π θ (x) = d i=1 θ * i θ i -1 π(x) θ J(x) (8)
The weight of each E i under π θ is proportional to θ * i /θ i ; In particular, all energy levels have the same weight 1/d under π θ * . The algorithm is then an importance sampling-like strategy, using π θ as the bias. Observe that points sampled according to π θ fall on average more in bins with underestimated density. Then the algorithm iterates the following two main steps:

• First, at each step, a point x is sampled according to π θ . More precisely, using µ = π θ in Eq. ( 7) yields a Markov kernel P π θ denoted P θ for the sake of conciseness; this kernel is used to sample its invariant distribution π θ .

• Second, multiply θ J(x) by an increment γ > 1 called the learning rate, and finally decrease the learning rate by a small fraction.

The way the learning rate γ is decreased calls for a short discussion. Historically, the Flat Histogram criterion was used [START_REF] Wang | Efficient, multiple-range random walk algorithm to calculate the density of states[END_REF]. Let ν t (i) be the number of samples up to iteration t falling into bin E i . The vector {ν t (i)} is said to verify the flat histogram (FH) criterion provided that, given a constant c:

max i=1,...,d | ν t (i) t -1/d |< 1 -c. (9)
If this criterion holds, γ is decreased using γ ← √ γ. Since log γ ← (1/2) log γ, this regime is called the exponential regime in the sequel. Unfortunately, this too fast rate yields an error known as the saturation error [START_REF] Belardinelli | Fast algorithm to calculate density of states[END_REF][START_REF] Belardinelli | Wang-Landau algorithm: A theoretical analysis of the saturation of the error[END_REF]. Also, the flat histogram variant is sensitive to the particular analytical form of the update rule [START_REF] Jacob | The Wang-Landau algorithm reaches the flat histogram criterion in finite time[END_REF]. To circumvent this difficulty, the γ t = exp(1/t) rule was proposed [START_REF] Belardinelli | Fast algorithm to calculate density of states[END_REF]. Practically, one combines the two update strategies by starting with the flat histogram and the exponential regime, switching to the 1/t rule as soon as γ is smaller than exp(1/t) [START_REF] Belardinelli | Fast algorithm to calculate density of states[END_REF].

The complete algorithm (Algo. 1) depends on the following parameters which influence its convergence speed: (i) the constant c for the flat histogram, (ii) the value of γ 0 , (iii) the energy discretisation, (iv) the proposal q.

Algorithm 1 Wang Landau Set exponential regime = False

13:

Set γ = exp( 1 t+1 )

14:

else 15:

γ = exp( 1 t+1 )

Theoretical convergence

A number of methods (auto-correlation as s function of the lag time, total variation distance, statistical tests) have been developed to assess the convergence of MCMC methods in particular and random processes in general [START_REF] Cowles | Markov chain Monte Carlo convergence diagnostics: a comparative review[END_REF][START_REF] Roberts | Optimal scaling for various Metropolis-Hastings algorithms[END_REF].

The convergence of WL is more challenging, since the algorithm uses a sequence of Markov kernels P θ . It has been studied in [START_REF] Fort | Convergence of the Wang-Landau algorithm[END_REF], using suitable assumptions on (i) the equilibrium measure, (ii) the Metropolis-Hastings kernel, and (iii) the sequence of learning rates. Under these assumptions, the authors proved a central-limit like theorem giving a theoretical convergence speed of O(1/ √ n) with n the number of steps.

Convergence rate: further insights

The convergence speed of the WL is tightly coupled to the mixing times of the Markov chains P θ , which depends on the proposal q. In [START_REF] Bornn | An adaptive interacting Wang-Landau algorithm for automatic density exploration[END_REF], a refinement rule for the discretisation is provided as well as a rule to find suitable parameters for a multi-modal Gaussian proposal. The paper does not establish any explicit link between the proposal and the discretisation. However, a symmetric proposal is used. Such proposal will sample the space uniformly. Hence, to obtain a high transition probability between two energy levels, the ratio of their respective volumes must be controlled: should this ratio be too small (or to high), the probability of proposing a move going from the smallest energy level to the biggest one vanishes. This obstruction vanishes for a non symmetric proposal, a strategy we will be using.

For multi-modal distributions, the difficulty to switch from one mode to another can also be a bottleneck for the mixing time. In [START_REF] Andricioaei | Smart darting Monte Carlo[END_REF], a strategy called darting is proposed. It consists in attempting long range jumps between regions associated to precomputed modes. The knowledge of the volume of the targeted regions allows one to guarantee detailed balance [START_REF] Sminchisescu | Generalized darting Monte Carlo[END_REF] whence a procedure sampling the desired distribution. Note that for molecular systems, where Boltzmann distribution yields one mode for each local minimum of the potential energy, local minima can be obtained by gradient descents and associated search methods such as basin hopping and variants [START_REF] Li | Monte Carlo-minimization approach to the multiple-minima problem in protein folding[END_REF][START_REF] Roth | Hybridizing rapidly growing random trees and basin hopping yields an improved exploration of energy landscapes[END_REF].

MCMC and adaptivity

For general MCMC algorithm, it has been shown that an adaptive Markov chain can lead to erroneous results [START_REF] Rosenthal | Coupling and ergodicity of adaptive MCMC[END_REF]. Practically, for a given probability π, there might exist a sequence P i of Markov kernels with limiting distribution π for all i such that for a given X 0 , the sequence of random variables defined by X i ∼ P i (X i-1 , .) does not converge to the limiting distribution π. This does not affect the Wang-Landau algorithm itself. However, any adaptivity must be stopped before the end of the algorithm. The choice we make is to stop any adaptivity once the flat histogram has been met a given number of times denoted N FHE in the sequel.

3 Methods: improving convergence speed

Rationale and difficulties targeted

Diffusivity across strata. As outlined in section 2, the convergence of the Wang-Landau algorithm largely relies on a suitable choice for the proposal q and the energy discretisation. In particular, a suitable proposal q and energy discretisation should leave no energy stratum poorly connected. The problem is stringent for energy strata near local minima and maxima where two difficulties are faced: accessing the strata, and leaving them.

For the particular case of local minima which is of interest in the sequel, accessing a low energy stratum is especially hard in high dimensional spaces: the volume of such strata being (in general) exponentially small in the dimension, they may be visited very seldom, resulting in an underestimation of the DoS θ i .

In turn, this underestimation makes it difficult to leave the stratum. To see why, assume that the stratum i has been reached, and that the proposal q attempts a move from say x ∈ E i to y ∈ E i+1 . By the M-H criterion Eq. ( 7) applied to the target distribution Eq. ( 8), this move is accepted with probability proportional to π(y) π(x)

θ J(x) θ J(y) q(y, x) q(x, y) . ( 10
)
Assuming that the ratio between q(y, x) and q(x, y) is bounded, if θ J(x) is severely underestimated, the move upward will be accepted with very low probability.

As suggested by this discussion, we aim for a ladder-like random walk connecting each energy level with the one bellow and the one on top with an as high as possible probability (Fig. 1). Such a random walk is termed diffusive. To this end, the following difficulties must be overcome by the proposal q:

• Difficulty 1: no overstep -section 3.3. To avoid overstepping strata, we introduce a topography adapted proposal which exploits the geometry of level set surfaces of the landscape.

• Difficulty 2: no congestion -section 3.4. We develop a high dimensional geometry aware biasing strategy to promote the effective move across strata. This strategy learns the right aperture angle of

E n E n-1 E 1 E 0 E n-2
Figure 1: Diffusivity between strata in WL.We consider a potential energy function U whose strata or energy levels are denoted

E i = {x ∈ E|U (x) ∈ [U i-1 , U i )}.
Energy levels may be seen as the nodes of a graph and may be connected in a variety of ways. In this work, we exploit a proposal q, which, via the Metropolis-Hastings criterion, connects strata in the WL algorithm in a ladder-like fashion. This strategy is especially well suited to sample a basin of arbitrary geometry.

cones encompassing the level set surfaces of strata below/above. In high dimensions, this is a difficult endeavor since proposals exploring uniformly the entire space face difficulties to hit these strata.

• Difficulty 3: multimodal distributions -section 3.5. To deal with the case of multimodal distributions, we resort to darting, a strategy meant to connect parts of the energy landscape which are separated by energetic or entropic barriers.

• Difficulty 4: energy range discretization -section 3.6. Slow convergence may be due to an inappropriate energy discretization. We resort to a refinement strategy to fix such problems.

Remark 1. It may be noticed that Eq. ( 10) simplifies in two settings: the first ratio is equal to one with π is uniform -see also Eq. 3; the last one is also equal to one when the proposal is symmetric. In that case, one is left with θ J(x)/θ J(y) .

Metrics to assess the diffusivity

We now introduce criteria to be correlated with the convergence of WL. We actually assess the notion of diffusivity just introduced in two ways: (i) using the moves proposed by q to study the diffusivity of the proposal, and (ii) using the moves proposed by q and processed by the WL M-H criterion to study the diffusivity of WL. To present the criteria based on these two types of moves, recall that there are d strata denoted E 1 , . . . , E d .

Descending times. As a global metric targeting moves accepted by WL, we resort to so-called descending times:

Definition. 1. A descent across d strata is defined by two times t 0 and t 1 such that

• x t0 ∈ E d and x t0-1 / ∈ E d . • x t1 ∈ E 1 and ∀t ∈ [t 0 , t 1 [, x t / ∈ E 1 .
The descending time is then t 1 -t 0 .

Aggregated transition matrices (ATM).

To further our analysis, we also define:

Definition. 2.
Consider an execution of WL. The aggregated transition matrix for q, denoted ATM q , is the d × (d + 1) row stochastic matrix providing the frequencies of transitions between strata corresponding to the moves proposed by q along the execution. (Nb: column d + 1 corresponds to moves ending outside the bounded region E.)

The aggregated transition matrix for W L, denoted ATM WL , is the d × d row stochastic matrix providing the frequencies of transitions within WL.

These definitions call for the following comments:

• The entries of the matrices are frequencies observed over an execution run of WL, rather than probabilities.

• For the sake of coherence, we represent matrices ATM q and ATM WL as d × (d + 1) matrices, even though the last column differs: it may be populated for ATM q , but is never so for ATM WL . Indeed, in the course of the WL algorithm, moves leaving the strata are rejected.

• Matrix ATM WL is not the matrix of a discrete Markov chain whose state space is the set of strata. Indeed, transitions are recorded for the evolving kernels P θ used in the course of the WL algorithm.

• Finally and most importantly, these matrices are meant to provide a concise encoding of the diffusivity of the random walks. In short, for a given row of either matrix, consider the connected components of the populated cells-that is the strata which are accessible from a given stratum. Ideally, one expects one connected component of width at least three, meaning that from a given stratum, one stays in place or visits the strata above and below in energy.

Remark 2. Descending times and aggregated transition matrices target different purposes. On the one hand, descending times only use the extreme strata, while transition matrices encode information involving all strata. On the other hand, descending times are easily localized. Consider a situation where the potential energy landscapes has two regions characterized by low and large descending times. Spatializing descending times, e.g. by clustering, is easier than defining localized aggregated transition matrices.

No overstepping across strata

Problem

Strata of small thickness tend to be stepped over. This typically happens when the landscape is steep or the discretization is fine. It is thus important to adapt the travel distance of the proposal in such regions. A Gaussian mixture identical for all strata has been used [START_REF] Bornn | An adaptive interacting Wang-Landau algorithm for automatic density exploration[END_REF]. However, the mixture is symmetric (see section 2.4) and does not exploit the geometry of the landscape.

Solution

Rationale. We estimate the local shape of the energy function using a Taylor expansion of the energy. We use an order two expansion since the gradient vanishes near local minima.

We first sample a vector u uniformly at random in the unit sphere S n-1 . We then compute the Taylor expansion in the direction of u with h ∈ R:

U (x + hu) = U (x) + h(∇U • u) + 1 2 h 2 (u T Hess u). (11)
Assuming that x ∈ E i , using the Taylor expansion, we compute the interval [h 0 , h 1 ] such that for h ∈ [h 0 , h 1 ] (Fig. 2)

x + hu ∈ E i (12) x 0 u H 1 H 2 E i E i+1 E i-1 H i = x 0 + h i u E i-2 H -1 H 0 Figure 2:
Proposal exploiting the geometry of the landscape to avoid overstepping strata: a move from x 0 ∈ E i should either stay in E i , move to E i-1 , or move to E i+1 . The intersection between a random line through x 0 with the level set surfaces of a quadratic approximation of the potential yields points

{H i } defining three segments [H -1 , H 0 ], [H 0 , H 1 ], [H 1 , H 2 ]
. Each such segment is chosen at random with probability 1/3, and a point is generated uniformly at random within the chosen segment. Note that the same random line can be obtained for two opposite vectors u and -u.

Doing the same for E i-1 and E i+1 yields [h -1 , h 0 ] and [h 1 , h 2 ]
. The last steps are to pick any of these 3 intervals with probability 1/3 and to sample h uniformly in the chosen interval. Doing so effectively adapts the proposal to the local shape of the energy landscape, allowing multiple scales. Even better, it also changes and adapts to the chosen direction.

Probability for the proposal. We now set up the formulae. Assume that the vector u is sampled uniformly at random in the unit sphere S n-1 . Also compute the h i from from the Taylor expansion at x in the direction of vector u = y-x y-x . Then, the probability density of going from x to y for any x and y with respect to the Lebesgue measure on {x + Ru} is

P no-overstep (x, y | u) = 1 {x+Ru} (y) 2 i=0 1 [hi-1,hi] (< y -x, u >) 1 3|h i -h i-1 | (13)
Consider also the uniform probability density on S n-1 :

P unif dir (u) = 1/Area(S n-1 ) = Γ(n/2) 2π n/2 (14)
Taking into account the fact that vectors u and -u yield the same intervals, and that we consider the sphere of radius y -x , the final proposal reads as

q unif no-overstep (x, y) = 2 1 y -x n-1 P unif dir y -x y -x P no-overstep x, y | u = y -x y -x . ( 15
)
Remark 3. Equation ( 11) explicitly uses the Hessian. In practice, the second order directional term is estimated numerically using the gradient.

Remark 4. To understand the interest of the previous calculation, the analysis of an overly simplified case is of interest. Assume that the domain E is a cube, and the level set surfaces bounding the strata are hyperplanes parallel to one face. We call the width W (E i ) of a stratum E i the distance between its two bounding planes. Assume the strata E ix x and E iy y are consecutive. It is easy to show using Thales theorem that if the boundary of the domain is not hit:

q unif no-overstep (y, x) q unif no-overstep (x, y) = W (E iy ) W (E ix ) .
Furthermore, in the cube:

W (E ix ) W (E iy ) = Volume(E ix ) Volume(E iy ) = θ * ix θ * iy .
Therefore, from Eq. ( 10), the acceptance ratio in Metropolis-Hastings (eq. 10) in Wang-Landau when the vector θ is close to θ * is close to 1. It effectively brings the asymptotic rejection rate of the Wang-Landau random walk to 0.

3.4

No congestion: dealing with high dimensionality and concentration

Problem

As noticed in section 3.1, we wish to design a proposal diffusing from E i to E i-1 and E i+1 . In the sequel, we present a strategy meeting this goal, based on a random direction in a suitable cone, in conjunction with the no overstep strategy from section 3.3. Our presentation focuses on moves downward which is helpful near local minima, yet readily generalizes to moves upward for the case of local maxima.

Consider the problem of lowering the energy by moving from stratum E i to E i-1 (Fig. 3), starting at point x 0 . To do so, a direction in a cone of angle α(x 0 , E i-1 ) must be chosen because directions outside this cone do not intersect E i-1 . As the dimension increases, the probability of sampling a point in a cone of fixed aperture decreases exponentially with the dimension (Fig. 4), preventing the proposal to reach the stratum E i-1 .

x 0

E i α(x 0 , E i-1 ) E i-1

Solution

Rationale. The most straightforward way to overcome this problem is to decrease the bin size. Indeed doing so makes α(x 0 , E i-1 ) closer to π/2. In practice, the bin splitting strategy from [START_REF] Bornn | An adaptive interacting Wang-Landau algorithm for automatic density exploration[END_REF] achieves this goal. However, the number of required strata increases with dimension, making this strategy less effective. Let C down (x 0 , E i-1 ) ⊂ S n-1 the subset of directions which allow moving into E i-1 from a point x 0 ∈ E i . Ideally, we could avoid splitting bins if we could bias the choice of direction towards this subset. An approximation of C down (x 0 , E i-1 ) could be found using a full second order Taylor expansion (thus requiring the full Hessian matrix). However this would be computationally very costly and the sampling procedure on such an approximation is unknown. Therefore, we limit ourselves to isotropic estimations of C down (x 0 , E i-1 ), i.e. C down (x 0 , E i-1 ) is estimated by an isotropic cone of angle α(x 0 , E i-1 ).

At a given point, consider the gradient of U . We take ∇U as the cone axis since it is the most natural candidate in the absence of additional information. In contrast, the aperture angle α(x 0 , E i-1 ) depends on the geometry of the level set bounding E i-1 -a global information unavailable. We bypass this problem by assuming that a single aperture α(E i , E i-1 ) is suitable for the majority of points in E i . This assumption holds if for example the curvature and width of stratum do not vary too much. The aperture can now be estimated during runtime. However, as noted in 2.5, adaptivity in MCMC algorithms can prevent convergence. Therefore, if the flat histogram criterion is used, we stop the learning procedure when the flat histogram criterion has been reached N FHE times .

Estimating the aperture angle. For a stratum E i , we wish to select an angle amidst a predefined set {α

(0) i , ..., α (k)
i }. We apply the following procedure-which is independent from the generation of x t+1 . For a given point x t ∈ E i sampled by Wang-Landau, consider the cones of apex x t , axis ∇U (x t ), and aperture angles α (j) i . We sample M vectors uniformly in each cone, and check for each of them whether the stratum E i-1 can be reached. Assume m points x t has been sampled. We compute for each cone the probability to reach E i-1 over the m × M vectors sampled. Since this probability is expected to be large for cones of small aperture, we pick the largest cone whose probability is larger than a user specified threshold p c . If no such angle exists, we use the fallback bin split strategy of section 3.6.

Probability for the proposal. Assume one knows how to sample uniformly at random a point in a cone, whence a random direction defined by the apex of the cone and that point -SI Section 6. With 1 cone (•) the indicator function of the cone, the corresponding probability reads as

P cone dir (u) = 1 cone (u)/Area(S n-1 ∩ cone). (16)
We introduce the following proposal based upon the no overstep proposal in the direction just chosen:

q cone no-overstep (x, y) = 2 1 y -x n-1 P cone dir y -x y -x P no-overstep x, y | u = y -x y -x (17)
Remark 5. Similarly to Eq. ( 15), Eq. ( 17) uses both vectors u and -u indistinguishably, even though our focus in on moving downwards. This is a design choice meant to make the implementation easier. In the worst case, a factor of two is lost to move downward.

Remark 6. The previous strategy, which uses a dictionary of cone apertures, calls for the following comments:

• The cone strategy combines local and non local pieces of information. The local information resides in the gradient. The non local information resides in the geometry of level set surfaces bounding the strata; this geometry is indeed accounted for indirectly by learning the right aperture angle. Using non local information makes it different from Hamiltonian Monte Carlo (HMC) [START_REF] Betancourt | A conceptual introduction to Hamiltonian Monte Carlo[END_REF] or Metropolis-adjusted Langevin algorithm (MALA) [START_REF] Girolami | Riemann manifold langevin and hamiltonian monte carlo methods[END_REF].

• The aperture angle of the cone is actually critical. Consider the set of directions delimited on S n-1 by a given cone. When the dimension increases, the mass of this set of directions concentrates on the boundary of the cone. Therefore, if the cone aperture is overestimated, sampled directions will end up with high probability in this region, and the corresponding proposal will miss the targeted stratum.

• Since the used cones are isotropic, one expects the method to be less efficient to handle highly non isotropic cases. However, moderately non isotropic cases are handled as well -see Experiments. • Even if a suitable cone is found by the previous procedure, the Metropolis-Hasting acceptance rate might be low -for instance if strata are too wide or if the curvatures of level sets non constant.

Handling multimodal distributions via darting

Problem

Classical proposals face difficulties to connect basins which are separated by energetic or entropic barriers (regions with high density of states but possibly no local minimum) [START_REF] Schön | entropically'stabilized region on the energy landscape of an ionic solid[END_REF][START_REF] Schön | Prediction, determination and validation of phase diagrams via the global study of energy landscapes[END_REF], inducing long mixing times.

Solution

Assuming one has a a priori knowledge of the positions m 1 , .., m K of theses minima, it is natural to introduce another type of move allowing jumps from one minima to another. To implement this, we use a darting strategy -see [START_REF] Andricioaei | Smart darting Monte Carlo[END_REF][START_REF] Sminchisescu | Generalized darting Monte Carlo[END_REF]. Darting in its simplest form defines a radius ρ, then adds transitions between the balls B(m i , ρ). In practice, if x t ∈ B(m i , ρ), one picks a ball at random-let j be its index, and proposes the following move: x t+1 ∼ U nif (B(m j , ρ)). However the balls B(m i , ρ) do not match the level set surfaces of their respective basins. Hence U (x t+1 ) -U (m j ) might be much larger than U (x t ) -U (m i ), leading to poor acceptance rates in the Wang-Landau algorithm.

Choice of the candidate point. Denoting m kt the local minimum whose basin contains x t , define ∆U t = U (x t ) -U (m kt ). Our rationale to optimize the acceptance ratio in Wang-Landau is to control both ∆U t -∆U t+1 and the ratio q(y, x)/q(x, y). For the former, we proceed as follows in two steps. First, we chose a target energy. For a given x t , let k be the index of the minimum chosen at random. For some β > 0, we choose a target energy

T U ∼ U nif (U (m k ) + ∆U t -β, U (m k ) + ∆U t + β). (18)
Second, we propose a point x t+1 such that U (x t+1 ) = T U (Fig. 6). To this end, we sample a vector u uniformly in the ellipsoid defined by v T H(k)v = 1 where H(k) is the Hessian of U at m k . Then we do a line search to find the intersection between the target energy T U and the half line m k + R + u (Fig. 5).

When to jump. The strategy just described requires a line search which is expensive if the target point is far from the local minimum. Furthermore, under some assumptions which are true if jumps are only allowed close to the local minima, the expression of the transition kernel can be simplified. Hence we introduce S a user defined parameter, and the darting proposal is only used if ∆U t ≤ S. While darting, the difference of energy with the local minima is controlled to monitor the acceptance rate.

∆U T U -U (m k ) x t x t+1 U m kt m k
Note that ∆U = U (x t ) -U (m kt ) and

T U ∼ U nif (U (m k ) + ∆U t -β, U (m k ) + ∆U t + β)
Transition kernel. Computing the transition kernel of the darting move is non trivial, but can be done using a suitable change of variables. The full computation is detailed in the appendix -section 7, however for the sake of conciseness, we only give here the final result. For any x and y in R n , let k be the closest minima to y, I k = [U (m k ) + ∆U -β, U (m k ) + ∆U + β], λ i and e i the eigenvalues and eigenvectors of the Hessian of U at m k . Finally, denoting < u, v > the dot product, let

l = i λ i < y -m k , e i > 2 . ( 19
)
Using the latter and denoting 1 I k (u) the indicator functor for the interval I k , the transition probability is given by:

q darting (x, y) = 1 K Γ n 2 2β 2π n 2 1 I k (U (y)) 1 l n ∇U (y) T (y -m k ) i≤n λ i . (20)

Splitting energy bins

Splitting an energy bin may prompt two scenarios: it can improve the mixing time of the random walk, and thus improve both the precision of the estimated DoS and the complexity to get it; or it has no effect on the mixing time, resulting an improvement of the precision at the expense of the computational burden. The goal is to refine bins in the former case only. Thus we only split bins when the cone strategy fails, as a fallback.

We monitor the failure of the cone strategy by computing the proportion of steps in which the random walk has the possibility to go up or down in energy (see 3.3 ) and the success rate of the Metropolis-Hasting criterion when going up or down. If either of these statistics are below a user defined threshold for a given bin, the bin is halved.

The final combined proposal

The final proposal combines the building blocks introduced in sections 3.3, 3.4 and 3.5, plus a Gaussian proposal with transition q gauss . Let p(x) = (p no-overstep (x), p gauss (x), p darting (x)) such that p no-overstep (x) + p gauss (x) + p darting (x) = 1 for all x ∈ R n . In addition, let p cone (x) < 1 be the probability of modifying the no overstep strategy by using the cone. The final proposal is

• choose one of the proposals at random with probability vector p(x t ),

• if the no overstep strategy is selected, use the cone with probability p cone (x) to choose the direction along which the proposal acts,

• sample the point x t+1 according to the chosen proposal.

The combined proposal therefore has the following transition probability: q(x, y) = p no-overstep (x) (1 -p cone (x))q unif no-overstep (x, y) + p cone (x)q cone no-overstep (x, y) + p darting (x)q darting (x, y) + p gauss (x)q gauss (x, y) (21) Remark 7. Eq. 21 calls for two comments:

• Since the proposal q is used in the Metropolis-Hastings algorithm, it is crucial to be able to compute q(x, y) for any x and y.

• The cone based strategy restricts the set of directions explored. The constraint p cone (x) < 1 leaves open the probability to pick any direction on the unit sphere.

Experiments

4.1 Setup

Implementation and parameters

Our implementation of a fully generic Wang-Landau algorithm is described in the companion paper [START_REF] Chevallier | A generic framework for Wang-Landau type algorithms[END_REF]. The corresponding C++ generic code, which allows tuning the physical system, as well as the main ingredients of the algorithm is currently being integrated to the Structural Biology Library -see [START_REF] Cazals | The Structural Bioinformatics Library: modeling in biomolecular science and beyond[END_REF] and http://sbl. inria.fr.

In the tests presented below, the initial number of strata d was specified along with each example. Otherwise, the following hyper-parameters were set as follows:

• Parameter from section 2.2:

-Flat histogram threshold: c = 0.1 for synthetic models, c = 0.05 for the molecule.

• Parameters from section 3.4:

k = 10 cones, with the associated aperture angles sampled uniformly in [0.2π/2, 0.8π/2],

-M = 1 direction sampled in a cone, p c = 0.4 as probability threshold to select the largest possible cone.

• Parameters from section 3.5

-Parameter S = ∞ and β = 0.001 used for darting.

• Parameters from section 3.7:

-Relative weights of the three components of the proposal, i.e. p no-overstep (x), p cone (x), p darting (x), p gauss . p cone (x) and p darting (x) are set to zero to turn off these strategies. Otherwise, the values are specified along with the examples.

Statistics of interest

Our experiments target three points: correctness, mixing time, and ability to handle complex systems. For the sake of conciseness, time t refers to t steps of Wang-Landau.

Correctness, stability, and convergence. When an analytical solution for θ * is known, we simply resort to the relative error for estimates at time t, defined by:

error(t) = i |θ * i -θ i (t)| θ * i . ( 22
)
We plot this function along time.

When no analytical solution is known-see the dialanine molecular model below, we assess convergence in two ways, based on several runs (N = 60). First, we plot an observable along time, akin to the partition function, at a fixed temperature:

Z λ(E) = 1 λ(E) E exp (-U (x)/kT ) ≈ Energy levels U θ * i exp (-U/kT ). ( 23
)
Second, we provide box plots on a per bin basis. We also resort to violin plots when more details are required in terms of distribution modes. (Recall that a violin plot displays a kernel density estimate of the data points processed.)

Mixing time. We use the descending times and the aggregated transition matrices-Section 3.1.

Remark 8. Note that we do not normalize the descending times by the number of strata. Indeed, as seen in section 3.6, increasing the number of strata can decrease the mixing time. Hence the number of strata is a parameter tuned for convergence speed and therefore should not be taken into account when measuring mixing time.

Contenders

As a yardstick, we compare our proposal (section 3.7) against the isotropic Gaussian proposals. However, while our proposal is used with its default parameters as specified above, the Gaussian variance needs to be tuned for a fair comparison [START_REF] Roberts | Optimal scaling for various Metropolis-Hastings algorithms[END_REF]. Hence we compare with 3 Gaussian proposals (resp. high, adequate and low variances).

Models

Analytical models. We study three analytical models. The first model is the isotropic harmonic potential.

The second is a non isotropic harmonic potential, to ensure that the algorithm behaves correctly in non trivial settings (Remark 6). The last model is a potential with two local minimum designed to study darting.

Molecular model. Finally, our last system is a classical toy molecular system, namely the blocked alanine peptide Ace-Ala-Nme (Fig 8), referred to as dialanine for the sake of conciseness. This system underwent extensive thermodynamic studies, using techniques as diverse as molecular dynamics [START_REF] Smith | The alanine dipeptide free energy surface in solution[END_REF], Monte Carlo and energy landscape based methods [START_REF] Somani | Energy landscapes and global thermodynamics for alanine peptides[END_REF], or dimensionality reduction methods [START_REF] Stamati | Application of nonlinear dimensionality reduction to characterize the conformational landscape of small peptides[END_REF]. We use the amber99-sb force field in vacuum and aim to compute the density of state between -21 kcal/mol and 4 kcal/mol associated to one local minima -by enforcing the simulation to remain inside the basin of this local minimum (φ = 59.8862, ψ = -35.5193). 24) for

x i ∈ [-1, 1], x i ∈ [-1/2, 1/2].

Ψ Φ

Results

Single well potential: isotropic

We study here the simple harmonic model

U (x) = x 2 i
with state space the unit ball in dimension n = 25. The energy discretisation is [a i , a i+1 ] with a i = i/10 for i ∈ {0..9}. The improved proposal is defined with p no-overstep = 1, p gauss = 0, p darting = 0, and p cone = 0.5. The flat histogram threshold is set to c = 0.1. Since the exact result is known, we plot the exact error.

Let us first focus on the error (Fig. 9(Left)). For the Gaussian proposals, the best scale is σ = 0.1, as smaller and larger values (resp. σ = 0.01 and σ = 1) yield large errors. Our proposal based on the no overstep alone is on par with the best Gaussian. Moreover, adding the cone yields the best results. This radical improvement owes to a descending time orders of magnitude smaller for the cone strategy (Fig. 9(Right)). These observations are coherent with the ATM matrices (Fig. 10), which show that (i) the proposals based on Gaussians face a high diversity in terms of strata reached, (ii) our proposal has an • The WL Metropolis-Hastings criterion also balances the probabilities to enter and leave a stratum, as shown by the comparable colors apart from the diagonal for ATM WL -as opposed to ATM q .

• While doing so, it refuses moves, which results in populating the diagonal.

• Matrix ATM q shows it is easier to climb strata than to go downhill.

Single well potential: non isotropic

To challenge all methods with a non-isotropic case (Remark 6), we use the following non isotropic potential energy:

U (x) = n i=1 ix 2 i
Also in dimension n = 25, the energy discretisation is [a i , a i+1 ] with a i = i/10 for i ∈ {0..9}. The improved proposal is defined with p no-overstep = 1, p gauss = 0, p darting = 0, and p cone = 0.5. The flat histogram threshold is set to c = 0.1. The results are on par with the isotropic case (SI Figs. 18 and19), showing in particular the effectiveness of the cone strategy in this anisotropic setting.

Dual wells potential: darting

To challenge darting, we use the usual one-dimensional dual well potential energy function x 4 -x 2 , and add a quadratic potential in other dimensions:

U (x) = x 4 1 -x 2 1 + n i=2 x 2 i . (24)
This potential energy has 2 local minimum at (-

, 0, ..., 0) (Fig. 7). The additional coordinates makes it harder to travel from one minimum to the other by making it hard to choose suitable directions. More specifically, direction x 1 corresponds to an energetic barrier, while the remaining directions add volume in phase space, which corresponds to an entropic barrier [START_REF] Schön | entropically'stabilized region on the energy landscape of an ionic solid[END_REF].

We setup the darting proposal with these two minima, and compare our proposal with and without darting. The energy discretisation is -0.25 < 0 < 0.2 < 0.4 < 0.6 < 0.8 < 1. The proposal is set up with p darting = 0.5, p no-overstep = 0.45, p gauss = 0.05, p cone = 0.5 when darting is enabled and p darting = 0, p no-overstep = 0.9, p gauss = 0.1, p cone = 0.5 when darting is disabled. The Gaussian move variance is set to σ = 1. The flat histogram threshold is set to c = 0.1.

Both methods yield correct values (Fig. 11(Left)). (Data not shown for darting disabled: since the potential energy function is symmetric for the first coordinate, the algorithm computes the correct value even if it never crosses the energy barrier.)

It appears that the proposal allows crossing the energy barrier almost instantly, while with darting disabled the first jump appears after 10 5 samples (Fig. 11(Right)). This induces a large difference in the mixing time.

Dialanine

On this system, the results reported thereafter were obtained using the cone improvement, as convergence could not be obtained without it.

To compute the value defined by Eq. ( 23) restricted to the basin of the local minimum with torsion angles, we enforce the simulation to remain within this basin. Checking whether a point is in a given minima basin of attraction requires a minimization of the potential energy. Since this is costly operation, we check this condition every N (=100) steps. If the random walk has escaped, we roll back to the latest point in this basin. (Note that this requires downgrading all statistics and random number generators [START_REF] Chevallier | A generic framework for Wang-Landau type algorithms[END_REF].) Remark 9. The roll back strategy just described may introduce some bias, as an excursion outside the basin may not be detected. The effectiveness of this strategy relies on a bounded proportion of roll backs, see [START_REF] Chevallier | A generic framework for Wang-Landau type algorithms[END_REF] for details.

We perform 60 runs, each with 10 7 steps. The energy discretisation can be found in Fig. 12(Top Right)). The proposal was set up with no darting and no Gaussian moves: p no-overstep = 1 and p cone = 0.6. The flat histogram threshold is set to c = 0.05.

To analyze convergence, we plot the time evolution of the observable defined from the partition function at T = (Eq. ( 23), Fig. 12(Top Left)). Since all simulations use the same number of bins, we also provide a box plot for each bin Fig. 12(Top Right)). Finally, to check whether the observable is unimodal or not, we perform a violin plot at three different time frames along the course of the simulation (Fig. 12(Bottom)).

We note that the convergence was reached to a different extent as a function of the volume of strata: the smaller the volume of a stratum, the higher the variance of estimates. This is expected as sampling rare events is always more challenging. It appears, though, that the observable converges (Fig. 12(Bottom)), since values concentrate along a single mode.

To get further insights, we study the contribution of individual strata reweighted by Boltzmann's factor (Fig. 13). We first note that the energy range used is sufficiently large since contributions of the last stratum is one order of magnitude smaller than the highest one (Fig. 13(Left)). The more detailed violin plots-not in log scale, also shows that distributions within strata are unimodal.

The analysis of ATM reveals two interesting facts. First, we first observe that without cone, moving downward is more challenging whatever the energy level (Fig. 14 bottom left, lower diagonal of ATM q ). The cone improves this state of affairs, even though the PEL is not isotropic -a priori. Second, we note that the moves proposed using the cone are accepted to a significant extent (Fig. 14, comparison of lower diagonals of ATM q and ATM WL .) One line or row corresponds to one stratum. For a given matrix line, the color coding indicates the probabilities (log scale) to move from a stratum to the remaining ones. Note that the matrices of our proposal are tridiagonal.

Conclusion and outlook

Contributions. Given a physical system characterized by an energy, the Wang-Landau (WL) algorithm is a stochastic method returning an estimation of the density of states in terms of histogram. WL is an adaptive Monte-Carlo method inherently using a discrete set of values whose pre-images in phase space define regions called strata. To compute the volume of these strata, a core component of WL is the proposal used to generate candidate conformations and navigate between the strata. In this work, we make an explicit link between the convergence of the Wang-Landau algorithm and the underlying proposal, developing of a novel composite proposal targeting the following three difficulties: avoiding overstepping strata, avoiding congestion -remaining trapped within strata, and accommodating multimodal distributions. The performances of our proposal are assessed by measuring so-called descending times which quantify the diffusivity across strata, and so-called aggregated transition matrices which encode the diffusivity across strata. All in all, the resulting Wang-Landau algorithm is effective to compute observables for small biomolecules, within hours on a laptop computer.

We believe that a key feature of our proposal is its ability to exploit non local geometric information in the following sense: the no overstep strategy exploits the geometry of level set surfaces bounding the strata; the cone strategy implicitly combines information on the gradient and the level set surfaces too; finally, darting exploits the a priori knowledge on the location of local minima. We note in passing that the WL algorithm based upon a proposal using geometric information beyond the gradient makes it different in spirit from methods such as HMC or MALA which only use local geometric information. In addition, WL is based on an energy discretization yielding a piecewise continuous target probability distribution, while HMC and MALA primarily target continuous models. In fact, the combination of the original WL with a geometry aware proposal bears similarities with the multi-phase Monte Carlo sampling methods used to compute the volume of polytopes in high-dimensional spaces, as in both cases, the algorithm exploits a discretization based on strata -in a sequential rather than global way for polytope volume calculations.

Further work. We foresee stimulating questions in three complementary directions: design, analysis, and applications. On the design front, the cone based strategy is rooted in the exploitation of the geometry of level set surfaces near one local minimum or maximum. Therefore, designing a similar strategy to handle the descent into multiple basins would open new perspectives, possibly in conjunction with topological persistence and darting. On the analysis side, since level set surfaces bounding the strata are used, it would be particularly important to understand how the choice of strata affects the convergence of WL, and see whether error bounds (rather than asymptotic estimates) can be obtained for DoS estimates. Along the way, an analysis connecting aggregated transition matrices and the convergence of Wang-Landau would be of high interest. Finally, on the application side, while our proposal operates in Cartesian coordinates, switching to internal coordinates is an appealing strategy to handle biomolecules whose conformational changes are best described by valence and torsion angles.

Spherical caps of the n-dimensional ball. We consider a conic region inside the n-dimensional ball, consisting of the union of a pyramid and that of a spherical cap defined by the cone of aperture α (Fig. 15). Surface and volume of such a cap is easily computed [START_REF] Li | Concise formulas for the area and volume of a hyperspherical cap[END_REF].

To compute the volume of the cap, we integrate the volume of a n -1 dimensional sphere or radius r sin β whose height element is d(r cos β) = r sin β:

V Cap n,α (r) = α 0 Vol n-1 (r sin β)d(r cos β) = Vol n (r) 2 I sin 2 α ( n + 1 2 , 1 2
).

Note that the incomplete Beta factor as the probability for a point of the ball to also be inside the spherical cap.

To compute the surface of the cap, we integrate the area of a n -1 dimensional sphere or radius r sin β with arc element rdβ:

A Cap n,α (r) = α 0 Area n-1 (r sin β)rdβ = Area n-1 (r) 2 I sin 2 α ( n -1 2 , 1 2
).

(36)

6.3 Algorithm to uniformly sample a hypercone

Sampling from f cap

The previous algorithm requires sampling from f cap defined in eq.( 28). The most straightforward way to sample from a probability density is to compute the inverse of the cumulative distribution function (F (x) =

x -∞ f (y)dy). This requires to compute a primitive of the density. However, there is no simple analytic expression for the primitive of f cap . Hence, we fall back to rejection sampling with a well chosen base distribution such that the rejection rate do note depend on the dimension n.

Observe that while (1 -l 2 )

n-1 2

do not have a simple primitive, the function l

(1 -l 2 ) n-1 2
do. Therefore we define

g cap (l) = M C cap l(1 -l 2 ) n-1 2 (37)
with M such that for all l, g cap (l) ≥ f cap (l) which is required for rejection sampling. The optimal choice for M is:

M = 1 L = 1 cosα .
L gcap the renormalized version of g cap . Assuming we can sample point from gcap , the acceptance rate for each l in the rejection algorithm used with f cap and g cap is

f cap (l) g cap (l) = 1 lM ≤ 1 M
as l ≤ 1. Hence the acceptance rate do not depend on n and only on α the opening of the cone.

Sampling from gcap : To sample from gc ap we compute the inverse of its cumulative distribution. Let

B(x) = x L l(1 -l 2 ) n-1 2 dl
using the change of variable y = 1 -l 2 , we deduce:

B(x) = - (1 -y 2 ) (1+n)/2 1 + n x L = (1 -L 2 ) (1+n)/2 1 + n - (1 -x 2 ) (1+n)/2 1 + n
The cumulative distribution for gcap is

F (x) = 1 x>L B(x) B(1) = 1 x>L 1 - (1 -x 2 ) (1+n)/2 (1 -L 2 ) (1+n)/2
And its inverse:

F -1 (x) = 1 -(1 -L 2 )(1 -x) 2/(n+1)
Hence we can sample from gcap .

Sampling from f cone

The inverse CDF for f cone is straightforward to compute:

F -1 cone (x) = Lx 1/n Therefore we can sample from f cone .

Changing the cone axis

The previous section algorithm generates a point in a cone whose axis is fixed: e 1 = (1, 0, ...0). In practice, the axis of a cone is aligned with the gradient of the potential energy -Section 3.4.

To handle arbitrary cones, we apply a linear transformation. We describe here how to apply this transformation with a contained complexity. Let d ∈ R n \ {e 1 } be the desired axis of the cone. Let H be the hyperplane orthogonal to e 1 . In the algorithm, we generates points in H. Suppose we generate (x 2 , ..., x n ) in H. For any orthonrmal basis 2 , ..., n of H, the points x 2 2 + ... + x n n will have the same distribution in H. Hence we try to find a basis 2 , ..., n adapted to our problem.

We choose 2 = d-<d,e1>e1 d-<d,e1>e1 . We complete this base with 3 , ..., n , and we will see that the choice of these 3 , ..., n do not matter. Let R the rotation such that R(e 1 ) = d and R( i ) = i for i > 2.

Let H 0 = V ect(e 1 ), H 1 = V ect(e 1 , 2 ) and H 2 = V ect( 3 , ..., n ). Let x ∈ R n . Then there exists u 1 , u 2 and v such that x = u 1 e 1 + u 2 2 + u 3 v with v = x-< x, e 1 > e 1 -< x, 2 > 2 ∈ H 2 . u 1 , u 2 and v are straightforward to compute. We easily get:

Derivation of the transition probability

Under assumption 1, f k is a bijection from S n-1 × [U (m k ), U (m k ) + M ] to the connected component containing m k of the set of point {y|U (y) ≤ U (m k ) + M }. Hence its inverse is well defined. The density of the pushfoward measure can be computed using the usual change of variable formula:

f k * (µ k,x )(y) = |J(f -1 k )(y)|1 I k (U (y))
For notation simplicity, we consider a fixed k and write f = f k and h = h k for the following computation. The inverse of f has the following expression:

f -1 (z) = z -m k z -m k , Ũ (z)
Let z = h(y) and u = z-m k z-m k , and choose w 1 , ..., w n-1 in R n such that w 1 , ..., w n-1 , u is an orthonormal basis of R n . Let l = z -m k . Then:

∂ f -1 ∂w i (z) = 1 l w i , ∂ Ũ ∂w i (y)
Observe that w 1 , ..., w n-1 is an orthonormal basis of the tangent space of S n-1 at u. Then considering that f -1 is an application from an open set of R n to S n-1 × R + , the Jacobian of f -1 becomes: The Jacobian matrix of h is easy to compute:

J( f -1 )(z) =       
|J(h)| = i≤n λ i
Hence we deduce:

f k * (µ k,x )(y) = 1 I k (U (y)) 1 l n ∇U (y) T (y -m k ) i≤n λ i (45)
The rescaling factor for measure µ k,x is:

µ k,x = 2π n 2 Γ n 2 2β (46)
Injecting equations 45 and 46 into equation 39 allows us to compute P dart (x, y).

Figure 3 :

 3 Figure 3: Reaching region E i-1 from E i near a local minimum: cone of suitable directions. Note that a similar problem is faced to move upward near a local maximum.

Figure 4 :

 4 Figure 4: Ratio between the area of the spherical cap subtained by an angle θ and that of the whole n-dimensional hemisphere S n-1 /2 -see Eq. (36 in Appendix. Ranges explored: dimension n ∈ [3, 100], and angle θ ∈ [0, π/2].

Figure 5 :

 5 Figure 5: Darting: reaching a prescribed energy level set via line search in the direction of vector u. The line search starts from minimum m k with target energy T arget.

Figure 6 :

 6 Figure 6: Handling multimodal distributions via darting: jumping between two local minima.While darting, the difference of energy with the local minima is controlled to monitor the acceptance rate. Note that ∆U = U (x t ) -U (m kt ) and T U ∼ U nif (U (m k ) + ∆U t -β, U (m k ) + ∆U t + β)

Figure 7 :

 7 Figure 7: Dual well function in dimension three. Plot of Eq. (24) forx i ∈ [-1, 1], x i ∈ [-1/2, 1/2].

Figure 8 :

 8 Figure 8: Dialanine (Ace-Ala-Nme) and the two dihedral angles Φ and Ψ

statistics for isotropic potential well in dimension 25 Figure 9 :

 259 Figure 9: Isotropic single well in dimension 25: comparison of the five proposals. Values have been averaged over 30 runs. The five proposals used are the three Gaussian based proposals, plus our combined proposal with and without the cone improvement. (Left) Comparison of the evolution of relative error -Eq. (22) (Right) Box plot of the descending times.

Figure 11 :

 11 Figure 11: Dual well potential in dimension 30: analysis of darting. (Left) Evolution of relative error of Eq. (22) when using darting. (Right) Comparison of time spent in the first well with and without darting.

Figure 12 :

 12 Figure 12: Analysis of convergence for dialanine, using amber-69sb force field in vacuum. Results averaged over 60 independent simulations. (Top Left) evolution of the partition function. (Top Right) Box plot of the estimation θ i for each bin i. (Bottom) Violin plot of the partition function at T = 300K, at three different time frames along the course of the simulation.

Figure 13 :

 13 Figure 13: Dialanine with amber-69sb force field in vacuum: analysis of convergence. Results averaged over 60 independent simulations. (Left) Box plot of the final bins volume with respect to the Boltzmann distribution at T = 300K. Log scale. (Right) Violin plot of the final bins volume with respect to the Boltzmann distribution at T = 300K

Figure 14 :

 14 Figure 14: Dialanine with amber-69sb force field in vacuum: aggregated transition matrices.One line or row corresponds to one stratum. For a given matrix line, the color coding indicates the probabilities (log scale) to move from a stratum to the remaining ones. Note that the matrices of our proposal are tridiagonal.

R 1 • 2 •Figure 16 :

 1216 Figure16: Not allowed by assumption 1 as there are multiple intersection point between a direction and the restriction of an energy level set to a basin.

m 1 m 2 U

 2 = T U basins boundary

Figure 17 :

 17 Figure 17: Not allowed by assumption 1 as selected directions yield intersection points outside the basin of m 1 .

  (z)|w 1 ) (∇ Ũ (z)|w 2 ) ... (∇ Ũ (z)|w n-1 ) (∇ Ũ (z)|u) f -1 )(z)| = 1 l n-1 (∇ Ũ (z)|u) And using Ũ (z) = U (h -1 (z)), ∂ Ũ ∂u (z) = ∇U (y) T J(h -1 )(z)u (41) = ∇U (y) T J(h -1 )(z) z -m k l (42) = ∇U (y) T J(h -1 )(z)(h(y) -m k ) 1 l (43) = ∇U (y) T (y -m k ) 1 l(44)Where the simplification in equation 44 is justified by the fact that h(y)-m k = J(h)(y-m k ) = J(h -1 ) -1 (ym k ).Combining the two previous equations:|J( f -1 )(z)| = 1 l n ∇U (y) T (y -m k )We deduce:|J(f -1 )(y)| = |J(h)| 1 l n ∇U (y) T (y -m k )

32

 32

time statistics for non isotropic potential well in dimension 25 Figure 18 :

 2518 Figure 18: Non isotropic single well in dimension 25: comparison of the five proposals. Values have been averaged over 30 runs. The five proposals used are the three Gaussian based proposals, plus our combined proposal with and without the cone improvement. (Left) Comparison of the evolution of relative error -Eq. (22) (Right) Box plot of the descending times.

1 :

 1 Set θ = (1/d, ..., 1/d) 2: Set exponential regime = True 3: Set γ = γ 0 with γ 0 > 1 4: while t < t max do Sample x t+1 ∼ P θ (x t , .)

	5:
	6:	Set θ J(xt+1) = γ θ J(xt+1)
	7:	Renormalise θ
	8:	if Exponential regime then
	9: 10:	if Flat histogram then γ = √ γ
	11:	if γ < exp( 1 t+1 ) then
	12:

Acknowledgments. The authors wish to thank the reviewers for their detailed comments, which were instrumental to streamline the contributions.

One line or row corresponds to one stratum. For a given matrix line, the color coding indicates the probabilities (log scale) to move from a stratum to the remaining ones. Note that the matrices of our proposal are tridiagonal.

Appendix: uniform sampling in a hypercone

We wish to sample uniformly at random in the intersection of a cone of aperture α intersected with a ndimensional ball B n (R) as described in Fig. 15. The procedure therefore yields a random point in the cone, and the direction defined by this point and the apex of the cone. The algorithm and the calculations use the notations of Fig. 15.

Uniform direction in a cone: algorithm overview

The classical strategy to uniformly sample on the unit sphere consists of picking a random vector of independent and identically distributed (iid) normally distributed random variables, and to normalize the obtained vector. In a similar spirit, to sample uniformly the intersection between a cone and the unit sphere S n-1 , we sample uniformly the intersection between the cone and the unit ball bounded by S n-1 , and renormalize the result. In the following, we sketch the algorithm, and refer the reader to the supplemental section for full details (Fig. 15 and supplemental section 6). The algorithm proceeds in three steps:

• (i) Decide whether one samples from the conic or the spherical regions,

• (ii) Pick a slice in the cone or spherical cap,

• (iii) Sample the slice.

More formally, consider a n -1 dimensional ball of radius 1 and the cone of angle α. We define:

• Vol n (1): the volume of the unit ball in dimension n,

• I x : the incomplete Beta factor -Def. in SI Section 6.2,

• the volumes of the conic and spherical regions respectively -Fig 15 and supplemental section 6:

Using these notations, the three aforementioned steps go as follows -details in section 6:

, we pick in the cone (i.e. l < L), else we pick in the cap (i.e. l > L).

• (ii) Pick a slice of the cone or the cap at distance l from the center, using the density

or

with C cone and C cap normalization constants used to define probability densities.

• (iii) Draw uniformly at random in the corresponding n -1 ball, using the density from Eq. (34).

Pre-requisites

Special functions. We shall need the Beta and incomplete Beta functions, defined by

Using both, one defines the regularized incomplete Beta factor

Spheres and balls: surface and volume. The surface area of a sphere of a n -1 sphere

The volume of the corresponding ball B n (R) satisfies

To generate a point X uniformly at random on the unit the unit sphere S n , we generate a point X = (x 1 , . . . , x n ) t whose coordinates are iid Gaussian with µ = 0 and σ = 1. The corresponding density is given by

To obtain a unit vector, we normalize the latter as X X . (NB: due to normalization the coordinates of this vector are not independent.) Random generation within a ball. To generate a point uniformly at random inside B n (R = 1), observe that the volume of B n (r) = r n V n . Differentiating yields

Therefore one generate a random value using the density dr n-1 for r ∈ [0, 1].

7 Appendix: transition probability for darting

Notations

We give here a detailed computation of the transition probability for darting given by eq. 20. We use the same notations than in section 3.5. Let us write P dart the Markov kernel associated to the darting move. Let x be a point of E. The transition kernel has a density, hence we write P (x, y) instead of P (x, dy). For a minimum k, let H(k) the Hessian of U at m k . Let λ 1 , ..., λ n its eigenvalues and e 1 , .., e n its eigenvectors as an orthonormal basis. Finally let A k ⊂ E be the basin of attraction of minimum k and let k x the minimum such that x ∈ A kx . We consider the following rescaling of state space:

Let Ũk (z) = U (h -1 k (z)) the potential energy in the rescaled space. Let fk (u, T U ) the application which associates the first intersection between m k + αu and Ũ = T U + U (m k ) with α > 0. Formally, fk is an application defined on S n-1 × R + .

Let

) be the pushforward measure of µ k,x by f k . Then, the Markov kernel seen as an operator on measures is given by:

where µ k,x is the product measure of the Lebesgue measure on S n-1 and the Lebesgue measure of

Assumptions

We first define assumptions ensuring that function f k defines a bijection between the set of directions and the restriction of the target energy level set surface to the basin of a local minimum. Intuitively, the level set surface seen from a local minimum should be star shaped, and the energy range considered should not contain any critical value associated with a saddle point. More formally: 16 and Fig. 17.

Doing a line search for every minimum is expensive. Using constant M defined in Section 3.5(see paragraph When to jump), we introduce the following assumption to simplify Eq. [START_REF] Stamati | Application of nonlinear dimensionality reduction to characterize the conformational landscape of small peptides[END_REF], which essentially states that the points considered belong to the Voronoi region of the local minimum m k : Assumption 2. For every y such that U (y) -U (m ky ) ≤ M , then for every k ≤ K, y -m ky ≤ y -m k The simplified expression for Eq. ( 39) reads as

where k y is the closest minimum to y. As a final observation, assumptions 1 and 2 are true if M is small enough (using a second order Taylor expansion for the proof at the bottom of the local minima)