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

Abstract:We study the computational effort required for global optimization of a smooth, possibly nonconvex objective $\Gamma:\mathbb{R}^d\to\mathbb{R}$. An algorithm satisfies the $(\varepsilon,\delta)$-PAC performance requirement if its output $\widehat X$ obeys $\mathbb{P}\{\Gamma(\widehat X)-\Gamma^\star>\varepsilon\}\leq\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/\delta)$ 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/\varepsilon$. For parallel fixed-temperature Langevin, an appropriate number of independent trials gives $ C_3=L^{1+o(1)}/\varepsilon$ as $\delta\downarrow0$, for each fixed $\varepsilon>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/(N\eta)\} +O(\log(1/\varepsilon))$, 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.

Optimization and Control (math.OC); Machine Learning (cs.LG)

arXiv:2609.06196 [math.OC]

(or arXiv:2609.06196v1 [math.OC] for this version)

https://doi.org/10.48550/arXiv.2609.06196 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.