arXiv preprint ·
Fast PAC Global Optimization via Restarted Langevin: Exploration, Exploitation, and Degenerate Cooling
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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δ$. 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/δ)$ 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 $δ\downarrow0$, for each fixed $\varepsilon>0$. The most substantial improvement comes from separating exploration from exploitation. If $η$ 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η)\} +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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Optimization & Control
The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization
1.73-Optimal Echelon Stock (R,nQ) Policies in Two-Stage Stochastic Serial Systems
Recovering linear images of sparse signals from indirect observations
Computation and Applications of Euclidean and Normed Representations of Massive Data
Adaptive stabilization of a leaderless bearing-constrained formation with disturbances
Get the few papers worth your time in Optimization & Control every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.