Global Optimization via Schr"odinger-F"ollmer Diffusion

We study the problem of finding global minimizers of V(x):ℝdrightarrowℝ approximately via sampling from a probability distribution μσ with density pσ(x)=dfracexp(-V(x)/σ)intmathbb Rd exp(-V(y)/σ) dy with respect to the Lebesgue measure for σ ∈ (0,1] small enough. We analyze a sampler based on the Euler-Maruyama discretization of the Schr"odinger-F"ollmer diffusion processes with stochastic approximation under appropriate assumptions on the step size s and the potential V. We prove that the output of the proposed sampler is an approximate global minimizer of V(x) with high probability at cost of sampling O(d3) standard normal random variables. Numerical studies illustrate the effectiveness of the proposed method and its superiority to the Langevin method.