Fast PAC Global Optimization via Restarted Langevin: Exploration, Exploitation, and Degenerate Cooling

We study the computational effort required for global optimization of a smooth, possibly nonconvex objective $Γ:\mathbb{R}^d\to\mathbb{R}$. An algorithm satisfies the $(\varepsilon,δ)$-PAC performance requirement if its output $\widehat X$ obeys $\mathbb{P}\{Γ(\widehat X)-Γ^\star>\varepsilon\}\leqδ$