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 $\mathrm{\Gamma }:{\mathbb{R}}^d\to \mathbb{R}$. An algorithm satisfies the $(\epsilon ,\delta )$-PAC performance requirement if its output $\widehat{X}$ obeys $\mathbb{P}\{\mathrm{\Gamma }(\widehat{X})-{\mathrm{\Gamma }}^{\star }>\epsilon \}\le \delta$. Algorithm design and analysis are in continuous time. We compare classical simulated annealing and fixed-temperature Langevin diffusion with two approaches introduced and analyzed here: parallel-restart Langevin and a Langevin–gradient scheme using stochastic dynamics for global exploration and gradient flow for local exploitation. Let $L=\log (1\mathrm{/}\delta )$ and let $E_{\ast }$ denote the dominant energy barrier. At logarithmic precision in the low-temperature regime, the first two approaches require simulation time exponential in $L\mathrm{/}\epsilon$. For parallel fixed-temperature Langevin, an appropriate number of independent trials gives $C_3=L^{1+o(1)}\mathrm{/}\epsilon$ as $\delta \downarrow 0$, for each fixed $\epsilon >0$. The most substantial improvement comes from separating exploration from exploitation. If $\eta$ is the attraction margin of a target region containing the global minimizers, a sufficient low-temperature estimate for total simulation time in the best-state Langevin–gradient variant is $C_4^{(c)}\approx N\exp \{EL\mathrm{/}(N\eta )\}+O(\log (1\mathrm{/}\epsilon ))$, with $E>E_{\ast }$. Thus global exploration is decoupled from the requested accuracy. Analysis beyond logarithmic precision reveals dimension-dependent prefactors, while experiments on the six-hump camel and Rastrigin objectives illustrate the benefits of warmer exploration and the usefulness of spectral information for understanding exploration time.