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

arXiv:2609.06196v1 Announce Type: cross Abstract: We study the computational effort required for global optimization of a smooth, possibly nonconvex objective Gamma:R^doR. An algorithm satisfies the (arepsilon,elta)-PAC performance requirement if its output widehat X obeys P{Gamma(widehat X)-Gamma^star>arepsilon}leqelta. 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/elta) and let E_* denote the dominant energy barrier. At logarithmic precision in the low-temperature regime, the first two approaches require simulation time exponential in L/arepsilon. For parallel fixed-temperature Langevin, an appropriate number of independent trials gives C_3=L^{1+o(1)}/arepsilon as eltaownarrow0, for each fixed arepsilon>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 Nexp{EL/(Neta)} +O(log(1/arepsilon)), with E>E_*. 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.

Source: arXiv cs.LG | 2026-09-09