Fast PAC Global Optimization via Restarted Langevin: Exploration, Exploitation, and Degenerate Cooling
Abstract
This paper addresses a fundamental question in non-convex optimization: \textit{How should a stochastic optimizer allocate computation between global exploration and local exploitation?} We study this question in continuous time, using Langevin dynamics for global exploration and deterministic gradient flow for local exploitation. The simplest algorithm in this class is the best-state Langevin--gradient method: several Langevin trajectories explore the objective landscape, the best state encountered is retained, and a single gradient trajectory then refines this state to high terminal accuracy. Our main objective is to characterize the computational work required to achieve a prescribed accuracy with prescribed confidence. We develop low-temperature approximations for this probably approximately correct (PAC) work--accuracy tradeoff, both for the best-state method and for related Langevin schemes. Global exploration is governed by energy barriers, through spectral-gap and Eyring--Kramers asymptotics. The resulting approximations expose the competing effects of temperature, computational budget, and the number of exploratory trajectories, and quantify their dependence on the confidence parameter. In contrast, terminal accuracy is largely separated from global exploration: once a suitable region of attraction has been reached, gradient flow requires only O(log(1/ε)) additional work to reach accuracy at least ε. Numerical experiments on challenging objectives serve to compare algorithms and to test the quantitative predictions of the asymptotic theory. They identify regimes in which the low-temperature approximations provide useful guidance, as well as regimes exhibiting substantial temperature sensitivity and potentially significant high-dimensional limitations.
Related
- Restarted Fixed-Point Acceleration of Proximal ADMM for Capped-ℓ1 Penalized Optimization
- Restarted Accelerated Primal-Dual Algorithms with Adaptive Stepsizes for Nonlinear Conic Constrained Convex Optimization
- Semi-discrete quadratic Wasserstein energy and state-dependent Langevin exploration
- Langevin for Nonconvex Optimization: Exact, Inexact and Zeroth-Order
- Global Convergence of Third-Order Langevin Dynamics for Non-Convex Optimization via Simulated Annealing
BibTeX
@misc{kontoyiannis2026fast,
title = {{Fast PAC Global Optimization via Restarted Langevin: Exploration, Exploitation, and Degenerate Cooling}},
author = {Ioannis Kontoyiannis and Sean Meyn},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06196},
eprint = {2609.06196},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06196},
}
RIS
TY - UNPB
TI - Fast PAC Global Optimization via Restarted Langevin: Exploration, Exploitation, and Degenerate Cooling
AU - Ioannis Kontoyiannis
AU - Sean Meyn
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.06196
UR - https://arxiv.org/abs/2609.06196
AB - This paper addresses a fundamental question in non-convex optimization: \textit{How should a stochastic optimizer allocate computation between global exploration and local exploitation?} We study this question in continuous time, using Langevin dynamics for global exploration and deterministic gradient flow for local exploitation. The simplest algorithm in this class is the best-state Langevin--gradient method: several Langevin trajectories explore the objective landscape, the best state encountered is retained, and a single gradient trajectory then refines this state to high terminal accuracy. Our main objective is to characterize the computational work required to achieve a prescribed accuracy with prescribed confidence. We develop low-temperature approximations for this probably approximately correct (PAC) work--accuracy tradeoff, both for the best-state method and for related Langevin schemes. Global exploration is governed by energy barriers, through spectral-gap and Eyring--Kramers asymptotics. The resulting approximations expose the competing effects of temperature, computational budget, and the number of exploratory trajectories, and quantify their dependence on the confidence parameter. In contrast, terminal accuracy is largely separated from global exploration: once a suitable region of attraction has been reached, gradient flow requires only O(log(1/ε)) additional work to reach accuracy at least ε. Numerical experiments on challenging objectives serve to compare algorithms and to test the quantitative predictions of the asymptotic theory. They identify regimes in which the low-temperature approximations provide useful guidance, as well as regimes exhibiting substantial temperature sensitivity and potentially significant high-dimensional limitations.
ER -